Neural Maximum Common Subgraph Detection with Guided Subgraph Extraction
Authors: Yunsheng Bai
Derek Xu
Ken Gu
Xueqing Wu
Agustin Marinovic
Christopher Ro
Yizhou Sun
Wei Wang
Venue:  (2020)
Keywords: graph matching
maximum common subgraph
graph neural networks
subgraph extraction
graph alignment

Abstract: Maximum Common Subgraph (MCS) is defined as the largest subgraph that is commonly present in both graphs of a graph pair. Exact MCS detection is NP-hard, and its state-of-the-art exact solver based on heuristic search is slow in practice without any time complexity guarantee. Given the huge importance of this task yet the lack of fast solver, we propose an efficient MCS detection algorithm, NeuralMCS, consisting of a novel neural network model that learns the node-node correspondence from the ground-truth MCS result, and a subgraph extraction procedure that uses the neural network output as guidance for final MCS prediction. The whole model guarantees polynomial time complexity with respect to the number of the nodes of the larger of the two input graphs. Experiments on four real graph datasets show that the proposed model is 48.1x faster than the exact solver and more accurate than all the existing competitive approximate approaches to MCS detection.

Under review as a conference paper at ICLR 2020
NEURAL MAXIMUM COMMON SUBGRAPH DETEC- TION WITH GUIDED SUBGRAPH EXTRACTION
Anonymous authors Paper under double-blind review
ABSTRACT
Maximum Common Subgraph (MCS) is defined the largest subgraph that is commonly present in both graphs of a graph pair. Exact MCS detection is NP- hard, and its state-of-the-art exact solver based on heuristic search is slow in prac- tice without any time complexity guarantee. Given the huge importance of this task yet the lack of fast solver, we propose an efficient MCS detection algorithm. NEURALMCS, consisting of novel neural network model that learns the node- node correspondence from the ground-truth MCS result, and a subgraph extraction procedure that uses the neural network output as guidance for final MCS predic- tion. The whole model guarantees polynomial time complexity with respect to the number of the nodes of the larger of the two input graphs. Experiments on four real graph datasets show that the proposed model is 31.78 x faster than the exact solver while achieving near near-perfect accuracy in MCS detection.
INTRODUCTION
Graph data are ubiquitous. Due to its flexible and expressive nature, graphs have heen used to store data of various domains. In computational biology, atomic networks can represent molecular compounds. In software analysis, program dependence graphs can describe the data and control dependencies. In social science, social networks can represent community structures. Because of graphs' unique ability to capture these data, algorithms tackling novel tasks on graphs across different domains have been gaining increased interest the representation learning community.
Graph matching, in particular, is recently popular task with new approaches such as Zanfir & Sminchisescu (2018), [Bai al. 2019a), and [L al, (2019). These methods either produce a score indicating how much and/or how well two graphs match or graph alignment indicating how and where two graphs match. The latter case is a far more difficult task than the former one. Current methods perform special case of graph alignment, namely image matching, where the two input graphs are of spatial structures (ex. pixel grids, object orientation, etc.) To account for more general graphs, we extract the Maximum Common Subgraph (MCS) (Bunke & Shearer [1988, widely used metric for graph alignment, and perform matching on the extracted subgraphs.
MCS is a very useful metric match two graphs in real-world applications. For example, in drug discovery, identifying compounds sharing similar substructures which tend to share similarity prop- erties can dramatically reduce the amount of molecules that need be manually tested (Ehrlich) & Rarey] 2011). In addition to molecular science, MCS also has application values in malware detection Park al. (2013), pattern recognition (Solnon et al. 2015), computer-aided circuit de- sign (Djoko et al. 1997] et al. 2012), etc. Unfortunately. MCS is NP-hard and, to the best of our knowledge, no existing algorithms tackle this problem from a purely machine learning approach.
We are among the first to tackle graph matching defined by MCS. This is more challenging than image matching or graph similarity computation, because MCS requires the extraction of the largest connected subgraph that is commonly present in both input graphs. This implies that the two ex- tracted subgraphs must not only be contained in both graphs but also be isomorphic to each other. To capture the MCS definition, our proposed model, NEURALMCS, fundamentally changes the way that the representations are learned. Instead of computing similarity all in one step, we introduce an iterative procedure match nodes one at time. By selecting nodes successively, tracted subgraphs are connected. We utilize subgraph embeddings to perform a stopping condition check, dealing with subgraph isomorphism and ending the procedure when the connected subgraphs
ensure the

---

Under review as a conference paper at ICLR 2020
Similarit
Scors
Figure 1: For graph pair (91: (2), previous works (Bai et al. 2019a 2018 predicting their graph-graphe similarity score. In this work, we aim to find the Maximum Common Subgraph (MCS) (circled in red), which requires fine-grained node-node correspondence prediction. It is more useful both due to the application value as described in Section [ and because of the interpretable similarity result indicated by the node-node mapping. Node text indicates node labels.
Li et al. 2019 focus
are the largest. By performing this iterative procedure, we both better ensure the isomorphism of the extracted subgraph as well as capture the recurrent relationship between matching pairs of nodes.
We experimentally verify NEURALMCSS on four real graph datasets. and show that NEURALMCS can achieve 48.1x x runtime gain over state-of-the-art exact MCS computation algorithm MC- SPLIT (McCreesh et al.] 2017), and is much more accurate than all the baseline approximate ap- proaches to graph matching.
PROBLEM DEFINITION AND PRELIMINARIES
2.1 PROBLEM DEFINITION
We denote graph as G EV) with node set V and edge set E. We define as induced subgraph as G' = (V', E') where V C V and E' E and E' preserves all edges between nodes in V in the original graph In other words, for two nodes in V' if there is edge between them in G, the induced subgraph must also contain the edge. In the rest of the paper, we use the term "subgraph" to refer to "induced subgraph".
In this work, our goal is to detect the Maximum Common Subgraph (MCS) for an input graph pair (9i, G2). general, MCS refers to the largest (induced) subgraph that is common to both graphs. In this paper, we make the following qualifications:
Labeled graph. The nodes of 91 and G2 are labeled, and nodes of different labels cannot be matched.
Connected subgraph. We require the detected subgraph to be connected, which is a com- mon qualification consistent with McCreesh et al.) (2017).
Our goal is to detect the MCS for input graph pair G1, G2. We adopt the state-of-the-art exact solver, McSPLIT (McCreesh et al. 2017), to provide ground-truth MCS results for a set of training graph pairs. Specifically, McSPLIT provides not only the nodes that are included in the MCS in both graphs, but also the node-node correspondence the MCS, as illustrated in Figure
2.2 NODE REPRESENTATION LEARNING
Among various node embedding methods, GRAPH MATCHING NETWORKS (GMN) L at 2019) are recent models designed for graph similarity computation. GMN is based on GRAPH CONVO- LUTIONAL NETWORKS (GCN) (Kipf & Welling 2016), but in addition to message passing within graph (intra-graph), GMN explicitly handles inter-graph information passing between the two input graphs.
First, GMN performs explicit cross-graph communication on node embeddings denoted as (!) where initial node features have I 0. More specifically, cross-graph communication is achieved
exp(eos(h." (9) ,a
through the following attention based mechanism: aب-ii Σ, expfco=(A." 1.95 Next, a softmax
function is applied to the cosine similarity between two node embeddings which makes sure similar node pairs across graphs receive greater attention. This weight is then multiplied with the difference
2

---

Under review as a conference paper at ICLR 2020
between cross-graph node embeddings to allow all node pairs in the two graphs to communicate with each other. Finally each node embedding resulted from inter-graph message passing con- catenated with embedding from intra- graaa neighborhood aggregation and placed through a MLP or a GRU core to complete a single layer update of h;-
THE PROPOSED APPROACH: NEURALMCS
Our proposed approach, NEURALMCS, relies on the learning capacity of the embedding model to generate a good matching matrix for each input graph pair, encoding the likelihood of each node- node pair being included the MCS and matched each other. Therefore, the training process aims to learn a matching matrix for each graph pair that is as close to the ground-truth node-node correspondence (as illustrated in Figure D as possible.
However, suppose that good matching matrix by itself is not enough for accurate prediction of the MCS. mainly due to the fact that MCS by definition requires the two extracted subgraphs must be isomorphic to each other and both subgraphs must also be connected (see Section 2.1). To satisfy these two requirements, we propose a novel GUIDED SUBGR APH EXTRACTION (GSE) process that iteratively performs guided search procedure to enlarge both extracted subgraphs using the matching matrix as guidance. The rest of the section details our proposed approach.
3.1 MATCHING MATRIX GENERATION
Our task fundamentally requires the matching between two graphs. Therefore, the ideal node em- beddings should receive information from the nodes of both graphs. Thus, we adopt the state-of-the- art node embedding model, GRAPH MATCHING NETWORKS (GMN), as described in Section 2.2 Specifically, we stack L GMN layers on the input node representations to allow inter-graph mes- sage passing multiple scales for sufficient interaction of the two graphs. We denote the final node
representations as U1 E x and U2 E R (x(x)(())
To match nodes from the input graphs, we compute the likelihood of matching each node in Gi to each node in G2. This likelihood indicates which node pair is most likely to be in the MCS, and should account for cases where some nodes in G1 do not match any nodes in G2 (and vice-versa). We naturally encode these likelihoods into matching matrix, Y E | |x
To compute Y, one can simply calculate the dot product between the node embeddings, U,U However, this resulting matrix is simply the similarity score between each pair of nodes in the two graphs, which is in the range of (- -inf, + inf) and requires further processing to reflect the probability of the node pair matched and being included in the MCS.
As this matrix encode the general similarity between nodes, we denote it as the similarity matrix, X. and further normalize obtain Y. Specifically, we perform the following transformations.
To find the likelihood of each node in one graph matching each node in the other graph, we apply column-wise and row-wise normalization on X.
exi
Pootn (i.j)
exie Prow (i.)
Ex,
To allow for some nodes to go unmatched, multiply these likelihoods by a value encoding the overall matching score of a node in one graph to nodes in the other graph.
Σ, Xaj [V2
Σ, Ex [V]
Pooin (i,j) = o
Pootn (i,j), Prow (I, o
Prow (i.j)
We consider both row-wise and column-wise normalization by taking the average of both scores, p(i.j) = Peote (Po and, to ensure we only select nodes with the same labels, we mask out node pairs with different labels to form Y.
3.2 LEARNING OF NEURALMCS
Although there exist multiple points where we can apply our loss function (before, during, or after GSE), found that applying binary cross entropy loss as early possible allows for GMN to
3

---

Under review as a conference paper at ICLR 2020
(a)
(b)
(c)
(d)
(e)
Matching
Matrix
Generation
()) Stopping
Condition
Reached
(k)
(g)
Figure 2: A detailed illustration of NEURALMCS using the example graph pair in Figure ! For the input graph pair (G1, G2), the NEURALMCS first generates matching matrix encoding the likelihood each pair of node being matched ((a) and (b)). The GUIDED SUBGRAPHI EXTRACTION (GSE) process uses the matching matrix as follows: NEURALMCS selects the initial pair to be included in the predicted MCS, node 2 in 91 and node G2 ((b) and (c)). Next, NEURALMCS the neighbors of the selected nodes, circled in dashed blue lines. By
sets its search frontier selecting the pair with the largest matching score which still preserves subgraph isomorphism, node 3 in 91 and node 5 in G2, the extracted subgraphs in both graphs grow size ((d) and (e)). The procedure continues until a stopping condition is reached, which is detailed in Section 3.3
receive better learning signal. For this reason, our loss function acts directly on the matching matrix.
Specifically, we design the following loss function to train the model L(Y) - E, L (og Mrlll where Yú denotes our predicted matching matrix and T denote an indicator value of whether the node matches node in the ground truth.
Since for a given graph pair, there can be multiple correct MCSs of equal size, we also employ multiple choice learning (Guzman-Rivera al. 2012 Li al. 2018). This is done by ensembling various copies of the model and propagating the loss function only through the copy which achieves the lowest loss, as shown by the following: L mLn))
3.3 GUIDED SUBGRAPH EXTRACTION (GSE)
Given matching matrix Y encoding the matching likelihood for all node pairs between 91 and G2- we propose the following GUIDED SUBGRAPH EXTRACTION (GSE) process. It starts by finding the most likely pair, and iteratively expands the extracted subgraphs by selecting one more node pair at a time. The procedure stops once the addition of any additional pair would lead to non-isomorphic subgraphs. summary, the proposed algorithm is shown in Algorithm A detailed illustration using an example pair from Figure is shown in Figure 2
The GSE algorithm internally maintains a binary assignment matrix T which will be the final output indicating the predicted MCS, and a masking matrix M, which is used to mask and select entries of the matching matrix Y. Both matrices are of the same dimension as Y. T initialized to all zero-size. M is initialized to all
zeros, indicating selected nodes, i.c. extracted subgraphs ones, since NEURALMCS may select any node pair for its initial subgraph.
To select the most likely node matching, the algorithm decides which pair of nodes should be lected (see Section 3.3.I for details) by order of their matching scores. This involves checking whether the selection of the pair would result in two isomorphic subgraphs
not. Only if so, the algorithm would select the pair (circled in red in Figure [ and include in the predicted MCS by node pair is included, GSE updates the mask M reflect the
updating Titgt tt to be 1. Once
4

---

Under review as a conference paper at ICLR 2020
Algorithm GUIDED SUBGRAPII EXTRACTION (GSE)
Input: (A1, A2), Y, node embeddings (U1, U2)
2: Output: Assignment matrix T.
3: Initialize < 0 Y.
initialize to all zeros
4: Initialize M < 1 Y.
initialize to all ones
5: Initialize update + True
6: while update True
7: I < sorted indices by highest to lowest value elements in M
8: for node pair (i..tt)ET
9:
update + False
Compute subgraph embeddings wi, w2 via Equation
11:
if [ - 22212 < {) subgraph isormorphism check
Select the found pair (it, ji) by updating Tt + +.
13: Expand the search frontier by updating the mask M via Equation
update f- True 15: break
search frontier for the next iteration (see Section 3.3.2 for details) and proceeds to the next iteration. Since the MCS by definiton requires the extracted subgraphs to connected graphs, we define the search frontier the first-order neighboring nodes of the current selected nodes. This guarantees the final predicted MCS satisfies the connectivity constraint described in Section
3.3. SUBGRAPH ISOMORPHISMM CHECK
To decide whether node pair (i! (i), from the search frontier can be selected or not, we check if the inclusion of node it in Gi and jf in G2 would result in two isomorphic subgraphs. To do this, we compute the two subgraph-level embeddings, w1 and W2 and check if their Euclidean distance is greater than a hyperparameter threshold e. A more detailed discussion can be found in Appendix H [
Computing the subgraph-level embeddings, however, involves more than simple aggregation of node embeddings from U₁ or U2. This because for subgraph isomorphism check, we are only concerned with nodes included in the subgraph. The nodes outside the selected subgraph should not affect the nodes inside. However, during node embedding generation, both intra- and inter-graph message passing are performed, resulting in U1 and U₂ containing unwanted information.
Inspired by the Weisfeiler-Lehmar (WL.) algorithm for approximate graph isomorphism test (Sher- vashidze et al., 2011), well as the connection between the WL algorithm and the GCNs, recompute the node embeddings by only aggregating neighboring nodes that are included in the current predicted MCS indicated by T:
((++1) A1 (v @ @U())), U (k+1) A2(u2 U,(,),,
{0, 13 are defined the row Tej. followed by setting Vist and U2ft to 1, and O U denotes element-wise multiplication, i.e. @U),, = uzUi,- For each graph, this performs message passing between nodes in the extracted subgraph plus the node it (for G1) or j (for G2). All the edges between these nodes are involved via the adjacency matrices A₁ and Ag. ensuring the subgraph is an induced subgraph required by the MCS definition as mentioned in Section 2.1
1351 and and column summation T. i.e. vi = Σソ Tıj. 02 = Vil
where A denotes the adjacency matrix, 01 E (0 13 |K5
The above updates are performed for K times to yield the final subgraph node embeddings denoted ((K) (x(()) and (K))) R(VS|xD(&) We finally compute the subgraph-level
By design of GSE, T guaranteed to be an assignment matrix, iee. there is at most one 1 for each row and column (see Section 3.3.2 Thus and are binary vectors indicating whether node is included in the subgraphs.
5

---

Under review as a conference paper at ICLR 2020
embeddings whose Euclidean distance is computed for apporximate subgraph isomorphism test:
Wi Ii ==1 (wn
(K)
(4)
W2 Σ 22
3.3.2 SEARCII FRONTIER EXPANSION
As the search process finds more node pairs, the mask M reflects the search frontier, i.e. the candidate node pairs for the next iteration to select from. Specifically, Mij denotes whether the node pair (i. should be candidate pair, and the sorting for node pairs performed on M Y.
Once node pair (i is selected by passing the check described in Section 3.3.1 GSE updates the search frontier by first obtaining two binary vectors indicating the neighbors of the selected nodes. Since each row of the adjacency matrix indicates the neighbors of the nodes of particular graph, and we need include neighbors of all the selected nodes, we first perform the following aggregation of rows of the adjacency matrix:
=
(2 Vil
A - v1), 22 A2 (1 02)-
U1
+ A
(5)
V/
P2
The (1 - v) term is for excluding the nodes that are already selected, which is key for ensuring that the next step does not select nodes that are already selected. This further guarantees that the final T matrix is an assignment matrix as required by Equation 3
To obtain binary indicator vector for the neighbors of selected nodes, we apply an element-wise indicator function, checking whether each entry of pı and P2 is greater than zero, yielding qı E (0, 1) I and Q2 E (0, 11aa,, Then we can obtain the updated mask M via
M X 92
(6)
where @ denotes the dyadic product of two vectors. This allows the selection to choose from the pairs formed by the nodes indicated by qi and q2.
3.4 OVERALL TIME COMPLEXITY
Each GMN layer involves the message passing for all node-node pairs, whose time complexity is quadratic with respect to the number of nodes. The matching matrix computation computes the dot product for all node-node pairs. The GSE process selects one node pair each time, and expands the search frontier by reaching to neighbors of selected nodes. Thus, GSE in the worst case reaches to all nodes of the smaller of the two input graphs, and each GSE step involves a quadratic mask computation. Therefore, NEURALMCS runs in O |/1 [V2]= * log * [V2])) time, where the size of the predicted MCS, which in the worst case is (in
4 EXPERIMENTS
We evaluate NEURALMCS on its accuracy and efficiency against the state-of-the-art exact MCS solver, MCSPLIT (McCreesh et al. 2017). and current machine learning approaches (Zanfir & Sminchisescul 2018 Wang al. 2019a Velickovic al. 2018 Li et al. 2019). on four real- world datasets, AIDS, LINUX, IMDB, and REDDIT from a diverse range of domains, Our basclines incldude the sfate-of-art MCS computation algorithm, McSPLIT (McCreesh al.) (017). IMAGE- GMN (Zanfir& & Sminchisescul 2018). IMAGE-PCA (Wang et al., 2019a). BASIC-GAT (Veliceiioovvi et al. 2018), and BASIC-GMN al. 2019). Appendix A and givie more details.
4.1
EVALUATION METRICS
For accuracy, we evaluate an exact and a soft metric:
Exact % ΣN C(Sn, S1) |(Ss/\/MMSs))
(7)
N

---

Under review as a conference paper at ICLR 2020
N Σx C(S,,,
1st 18,22 2/MCS;
Soft %
N
where N is the number of graph pairs in the testing set; S and S/2 the subgraphs extracted from the first and second graph, respectively; C(s is a function that returns if the two input graphs are isomorphic each other and otherwise; is the indicator function that returns 1 when the condition is true and otherwise; [MCS;] the true MCS size. For efficiency, we evaluate the average running time across graph pairs.
4.2 RESULTS
We see that in terms of accuracy, NEURALMCS improves current methods of subgraph extraction substantially, especially on the AIDS and LINUX datasets, where NEURALMCS performs close to the ground truth solver. For IMDB and REDDIT, the performance is also drastically higher than the baselines. Most interestingly, we find that, when the model does not find the exact ground-truth solution, it still extracts high-quality subgraphs with sizes average above 90% of the true MCS size, where all graphs are isomorphic (see Appendix E). The poor performance of computer vision baselines IMAGE-GMN and IMAGE-PCA suggests that the assumptions for image matching do not work for MCS based graph matching very well. Appendix [F provides a thorough analysis of the performance boost from each component of the proposed model compared with various alternative designs. Compared against the 2 basic models, we see that both the representation learning scheme and the extraction strategy greatly enhance the performance the model. The exact accuracy results can be seen in Table
Table 1: Exact % and Soft % accuracy metrics across four real graph datasets. All methods have been adapted for the MCS detection task. McSPLIT is the ground-truth MCS solver labeled with *
AIDS
LINUX
IMDB
REDDIT
Method
Exact %
Soft
Exact %
Soft %
Exact %
Soft %
Exact
Soft %
McSPLIT
100.000
100.000
100.000
100.000
100.000
100.000
100.000
100.000
IMAGE-GMI
0.033
0.033
19.790
19.790
N/A
N/A
20.261
20.261
IMAGE-PCA
0.229
0,229
22.693
22.693
38.582
38.582
33.987
33.987
BASIC-GAT
11,013
22.199
41.135
53.070
47.462
51.680
37.908
50.196
BASIC-GMN
12,488
19.256
48.082
52.590
55.273
62.738
43.137
51.782
NEURALMCS
98.525
99.626
99.674
99.955
97.235
99.613
96.078
99.562
terms efficiency, NEURALMCS 31.78x faster than the ground-truit solver averaged across the four datasets, while being slightly slower than the baselines.
However, as shown Table ! the baseline methods fail consider the connectivity and subgraph isomorphism constraints during maximum common subgraph extraction resulting in worse accuracy. The exact performance results can be seen in Figure 3
10
UNUX
307
IMDS
Average Runtime
ac*
Mcsple
Figure 3: Running time comparison.
4.3
CASE STUDY
The iterative expansion ensures that extracted subgraphs satisfy the connectivity constraint. The representation learning component ensures that we select the correct node at each step. As seen in Figure 4 for the AIDS dataset, the learnalle matching matrix helps NEURALMCS select good nodes, and, for the IMDB dataset, the iterative procedure indeed helps our model stop once adding additional nodes would break the isomorphism constraint. More importantly, our model is also able to solve both the subgraph isomorphism and graph matching problems. Additional case studies and analysis can be found in Appendix

---

Under review as a conference paper at ICLR 2020
(a) AIDS
(b) LINUX
(c) IMDB
(d) REDDIT
Figure 4: Case study: Three MCS examples from each dataset. AIDS has node labels node text. For clarity, we draw only two node-node correspondences for each example, represented as dashed lines between nodes in the two graphs.
5 RELATED WORK
Graph isomorphism is classic problem that goes back to at least the early work by Sussenguth (1965) and Corneil & Gotlieb (1770.. Recently [abai] (2016) shows that graph isomorphism can be solved in quasipolynomia time. However, graph isomorphism is only concerned with whether two graphs are exactly the same or not, which may too rigid in real-world applications. For example, what if two graphs not isomorphic? In such scenario, more useful output can be the similarity (or distance) between them, defined by metrics such as Graph Edit Distance (GED) (Bunke 1983
Maximum Common Subgraph (MCS) (Bunke & Shearer 1998
Bunke 1997).
In this work, we focus on the more challenging task of graph matching, specifically the matching of two graphs defined by the MCS metric. The MCS detection problem is NP-hard, and remain com- putationally challenging. Existing works use constraint programming (Vismara & Valery 2008 McCreesh et al., 2016), branch-and-bound (McCreesh et al.) 2017 Liu et al.j 2019), mathematical programming (Bahiense et al., (2022). reduction to maximum clique detection (Levi, 1973 Mc- Creesh al. 2016), etc. MCS has many definitions tailored different graph types and application specifics (McCreesh et al., 2017). and is Nomain-agnosti metric to compare graphs in detailed way, so has occurred widely in applications such as graph database systems (Yan et al. 2005). cloud computing platforms (Cao et al., 2011). etc.
The term "graph matching" is very general and has been adopted by many recent works: (1) Graph similarity computation (Bai et al. 2019a Li et al.] 2019) aims to output similarity score for an input graph pair, which can be defined by the MCS metric but less challenging due to the score output. (2) Image matching is classic task in computer vision with traditional approaches based on quadratic assignment problem solving (Zhou & De Torre 2012 Yu et al. (0188) and more recent methods using neural networks
-MMN (Zanfir & Sminchisescu, 2018) and IMAGE- PCA (Wang et al., 2019a)). (3) The two-graph alignment (Heimann et al. 20188] [5[Xu et al., (2019) problem deals with the alignment of two general structured graph objects. However, the alignment is typically not defined by domain-agnostic metrics such as GED or MCS. There currently no such methods learning from ground-truth graph pairs to the best of our knowledge.
CONCLUSION
In this paper, we propose a neural network approach to solve the NP-hard problem, Maximum Common Subgraph (MCS) detection, in approximate and accurate way. For input graph pair, our model NEURALMCS computes the likelihood of each pair of nodes being included in the MCS and matched, which is used by the proposed GUIDED SUBGRAPII EXTRACTION (GSE) algorithm to iteratively include more and more nodes in the predicted MCS. The whole model runs in polynomial time complexity, and experimental results four real graph datasets demonstrate that NEURALMCS is 31.78x x faster than the exact solver whole achieving very good accuracy compared series of strong approximate graph matching baseline approaches.
8

---

query over Under review as a conference paper at ICLR 2020
REFERENCES
László Babai. Graph isomorphism in quasipolynomial time. In STOC, pp. 684-697. ACM, 2016.
Laura Bahiense, Gordana Manić, Breno Piva, and Cid C De Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, 160(18):2523- 2541, 2012.
Yunsheng Bai, Hao Ding, Yizhou Sun, and Wei Wang. Convolutional set matching for graph simi- larity. NewrlPS Workshop on Relational Representation Learning Workshop, 2018.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. WSDM, 2019a.
Yunsheng Bai, Hao Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Ting Chen, Yizhou Sun, and Wei Wang. Unsupervised inductive whole-graph embedding by preserving graph proximity. IJCAI, 2019b.
Albert-Láásıóó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Horst Bunke. What the distance between graphs. Bulletin of the EATCS, 20:35-39, 1983.
Horst Bunke. On relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters, 18(8):689-694, 1997.
Horst Bunke and Kim Shearer. A graph distance metrie based on the maximal common subgraph. Pattern recognition letters, 19(3-4):255225 259,, 1998.
Ning Cao, Zhenyu Yang, Cong Wang, Kui Ren, and Wenjing Lou. encrypted graph-structured data in cloud computing. In 2011 31st International Conference on Distributed Computing Systems, pp. 393-403- IEEE, 2011.
Derek Gordon Corneil and Calvin C Gotlieb. An efficient algorithm for graph isomorphism, of the ACM (JACM), 17(1):51-64, 1970.
Surnjani Djoko, Diane J. Cook, and Lawrence B. Holder. An empirical study of domain knowledge and its benefits to substructure discovery. TKDE, (4):5775-566 1997.
Hans- Chrrissann Ehrlich and Matthias Rarey. Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review. Wiley Interdisciplinary Reviews: Computa- tional Molecular Science, 1(1):68-79 201
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Abner Sarrman-Riveras Dhruv Batra, and Pushmeet Kohli. Multiple choice learning: Learning to produce multiple structured outputs. In NeurIPS, pp. 1799-1807, 2012.
Mark Heimann, Haoming Shen, Tara Safavi, and Danai Koutra. Regal: Representation learning- based graph alignment. In CIKM, pp. 117-126. ACM, 2018.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. ICLR, 2016.
Philip A Knight. The sinkhorn-knopp algorithm: convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30(1) 30(1):261 -:251-275, 2008.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2)833-77 1955.
Der-Tsai Lee and Bruce Schachter. Two algorithms for constructing a delaunay triangulation. International Journal of Computer Information Sciences, 93):219-242, 1980.

---

Under review as a conference paper at ICLR 2020
Giorgio Levi. A note the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo, 944)341, 1973.
Wenchao Li, Zach Wasson, and Sanjit A Seshia. Reverse engineering circuits using behavioral pattern mining. In 2012 IEEE international symposium hardware-oriented security and trust, pp. 83-88. IEEE, 2012.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity graph structured objects. ICML, 2019.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In NeurIPS, pp. 539-548, 2018.
Yongjiang Liang and Peixiang Zhao. Similarity search in graph databases: A multi-layered indexing approach. In ICDE, pp. 783-794. IEEE, 2017.
Yan-li Liu, Chu-min Li, Hua Jiang, and Kun He. learning based branch and bound for maximum common subgraph problems. ICAI,, 2019.
Ciaran McCreesh, Samba Ndojh Ndiaye, Patrick Prosser, and Christine Solnon. Clique and con- straint models for maximum common (connected) subgraph problems. In International Confer- ence on Principles and Practice of Constraint Programming, pp. 350-368. Springer, 2016.
Ciaran McCreesh, Patrick Prosser, and James Trimble. A partitioning algorithm for maximum com- mon subgraph problems. 2017.
Younghee Park, Douglas S Reeves, and Mark Stamp. Deriving common malware behavior through graph clustering. Computers & Security, 39:419-430, 2013.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-Iehman graph kernels. JMLR, 1255p))253,- 2011.
Christine Solnon, Guillaume Damiand, Colin De La Higuera, and Jean- -hrr-thisttophe Janodet. On the complexity of submap isomorphism and maximum common submap problems. Pattern Recogni- tion, 48()):302233111 2015.
Edward H Sussenguth. A graph-theoretic algorithm for matching chemical structures. Journal of Chemical Documentation, 5(1):36-43, 1965.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
Philippe Vismara and Benoît Valery. Finding maximum common connected subgraphs using clique detection constraint satisfaction algorithms. In International Conference on Modelling, Com- putation and Optimization in Information Systems and Management Sciences, pp. 358-368. Springer, 2008
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching, ICCV, 2019a.
Xiaoli Wang, Xiaofeng Ding, Anthony KH Tung, Shanshan Ying, and Hai Jin. An efficient graph indexing method. ICDE, pp. 210-221. IEEE, 2012.
Yue Wang and Justin M Solomon. Deep closest point: Learning representations point cloud registration. ICCV, 2019.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning on point clouds. ACM Transactions on Graphics (TOG), 38(5): 146, 2019b.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Grosevvwwaserrseiin learning for graph matching and node embedding. JCML, 2019.
Xifeng Yan, Philip S Yu, and Jiawei Han. Substructure similarity search in graph databases. In SIGMOD, pp. 766-777. ACM, 2005.
10

---

Under review as a conference paper at ICLR 2020
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In SIGKDD, pp. 1365-1374, ACM, 2015.
Tianshu Yu, Junchi Yan, Yilin Wang, Wei Liu, et al. Generalizing graph matching beyond quadratic assignment model. In NewrlPS, pp. 853-863, 2018.
Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In CVPR, pp. 2684- 2693, 2018.
Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. PVLDB, 2(1):25 36, 2009.
Xinyi Zhang and Lihui Chen. Capsule graph neural network. ICLR, 2019.
Xiang Zhao, Chuan Xiao, Xuemin Lin, Qing Liu, and Wenjie Zhang, A partition-based approach to structure similarity search. PVLDB, 7(3):169-180, 2013.
Weiguo Zheng. Lei Zou, Xiang Lian, Dong Wang, and Dongyan Zhao. Graph similarity search with edit distance constraint in large graph databases. CIKM, pp. 1595-1600. ACM, 2013.
Feng Zhou and Fernando De la Torre. Factorized graph matching. In CVPR, pp. 127-134. IEEE, 2012.
A DATASET DESCRIPTION
We run experiments on 4 diverse different real world datasets coming from the chemical, pro- gramming language, and social network domains. For each dataset, split the pairs into train- ing, validation, and testing sets in the ratio of 6:2:2 such that none the training, validation, testing sets share any common graphs. For each dataset, bels, if the dataset has node labels, or provide the same initial encoding, if the dataset does not have node labels. The code and the datasets have been published to this anonymous link:
either one-hot encode node la-
A.1 AIDS
AIDS dataset of antivirus screen chemical compounds, coming from the Developmental Ther-
apeutiis Program at NCI/NIH² The AIDS dataset has been used by various works in graph match- ing (Zeng et al. |009 Wang et al. 2012) Zheng al., 2013 Zhao et al.) [2013] Liang & Zhao [017]] Bai et al. 2019a). These graphs consist of labeled nodes and unlabeled edges, where nodes represent chemical elements (ex. Carbon, Nitrogen, Chlorine, and etc.) and edges represent bonds between atoms. There are total of 700 graphs, from which we sample 29610 graph pairs. The average graph
size is 8.664 with the largest graph having 10 nodes.
A.2 LINUX
LINUX is a dataset of program dependence graphs (PDG) describing individual functions generated from the Linux kernel (Wang et al.] 2012).. These graphs consist of unlabeled nodes and unlabeled edges, where nodes represent statements and edges represent control flow between statements. There are a total of 1000 graphs, from which we sample 601 14 graph pairs. The average graph size is 7.591 and the largest graphs have 10 nodes.
A.3 IMDB
IMDB is a dataset of ego-networks of movie actors/actresses from the IMDB website (Yanardag & Vishwanathan 2015). This dataset has been used by various works in graph classification (Zhang & Chen 2019 Bai et al. 2019b). These graphs consist of unlabeled nodes and unlabeled edges, where nodes represent actors/actresses and edges represent whether they have had collaborations. There are a total of 1500 graphs, from which we sample 135702 graph pairs. The average graph size is 12.981 and the largest graphs have 89 nodes.
httpps:/wiix nci. nih httpp//hh......aaaa//////ttt//aa

---

Under review as a conference paper at ICLR 2020
A.4 REDDIT
REDDIT is dataset of online dicussion networks from the Reddit online discussion website (Y-- nardag & Vishwanathan 2013). These graphs consist of unlabeled nodes and unlabeled edges, where nodes represent users and edges represent whether users have responded to eachother's com- ments. There are a total of 7112 graphs, from which we sample 3556 pairs. The average graph size is 1 11.8 nodes and the largest graph has 16 nodes.
B BASELINES
We evaluate NEURALMCS against the state-of-the-art solver, McSPLIT. which uses heuristics and the branch and bound algorithm to achieve efficient computation for MCS. While the fastest among exact solvers, this method still has, in the worst case, exponential time complexity (McCreesh al, 2017). For this reason, in practice, its running time is much slower than the other approximate baselines. However, still use McSPLIT generate ground-truth MCS results and it only takes a few days on a standard CPU server with multi- multi-threading to handle all the ground-truth result generation.
The representation learning baselines are adapted from recent graph matching techniques, specifi- cally IMAGE-GMN (Zanfir & Sminchisescul 2018) and IMAGE-PCA (Permutation Loss and Cross- graph Affinity) (Wang et al. (2119a). Both these methods utilize similarity scores and normalization to perform graph matching. As IMAGE-GMN uses CNN layers form their node embeddings from images (with techniques such as Delaunay triangulation (Lee & Schachter 1980)), we adapt the model our task by replacing these layers with GAT layers, consistent with NEURALMCS. MIAGEEPPCA uses a node embedding mechanism similar to GMN, not requiring further adaptation. As the loss functions for both these methods were designed for image graphs, we alter their loss functions to binary cross entropy loss (the same as MESRALMCS).
We conduct the extraction process by first removing all nodes where its corresponding summation of similarity scores across rows columns falls below tuneable threshold (the values of which can be found in Appendix C) in the matching matrix, then selecting an equal number of nodes in both graphs. The latter is done by maximizing the similarity scores of uniquely selected node pairs through applying the Hungarian Algorithm (Kuhn) 1955) on the remaining nodes of the matching matrix. This is because the extracted subgraphs, after just thresholding, may be of different sizes due to thresholding. The extra procedure ensures that we extract subgraphs of equal sizes and in addition, the Hungarian Algorithm yields one-to-one node-node correspondences for the extracted subgraphs. However, these methods do not necessarily result in isomorphic subgraphs.
We also compare against two basic models, BASIC-GAT (Velickovic et al. 2018) and BASIC- GMN (i et al. 2019), which use 3 GAT and GMN layers respectively to encode the initial node features, followed by similarity score computation. These baselines uses a simpler normalization scheme by appling element- wise sigmoid function (y = 1/(1 + e e"") to the matching matrix, and directly feed the similarity matrix to the same loss function as defined by NEURALMCS. BASIC- GAT and BASIC-GMN use the same extraction method as the graph matching baselines.
With exception to McSPLIT, all these baselines run in polynomial time complexity with respect to the number of nodes in the two input graphs.
C PARAMETER SETTINGS
For our model, we utilize 3 layers of GMN with 64 dimensions each for the initial embedding. We use ReLU(x)= = max (0, .) as our activation function. We fix the number of outputs for multiple choice learning to 10 on the AIDS, LINUX, and REDDIT datasets, and to 3 on the IMDB dataset. To evaluate the efficacy of multiple choice learning, we also use the same technique and settings for BASIC-GAT and BASIC-GMN. We set to 10-4, to account for numerical errors during floating point arithmetic. For the extraction procedure in our baselines, we set the threshold to 0.5 on the AIDS, LINUX, and REDDIT datasets, and to 0.7 on the IMDB dataset. We ran all experiments with Intel i7-6800K CPU and one Nvidia Titan GPU. For training, we set the batch size to 64, the learning rate 0.001, the number of iterations to 5000, and use the Adam optimizer (Kingma & Ba
12

---

Under review as a conference paper at ICLR 2020
2013 All experiments were implemented with the PyTorch and PyTorch Geometric libraries (Fey & Lenssen 2019).
For more dataset setup and training/valicaaiionesstigg splits, please refer to Appendix A For more on baseline setups, including their extraction procedure, please refer to Appendix B For more on the extraction procedure of NEURALMCS, please refer to the main text.
D DETAILS ON EVALUATION PROCEDURE
As mentioned in Section 4.1 for graph pair i in the test set, we first check whether the predicted MCS satisfies the MCS constraints not. In this section we give more details.
Denote the extracted subgraphs from the i-th graph pair as Sa and S22, respectively. The MCS constraint satisfaction check includes the following steps: First, we check if S and S/2 are both connected (i.e. no isolated components); Second, we check S and S/2 are isomorphic to each other. Since exact isomorphism checking may take long time in practice, isomorphism checking, and when timeout happens, we switch to an approximate checker The timeout well as the whole procedure is applied across all the methods to ensure fair comparison.
set timeout for exact
When we generate Sn1 and S22 for NEURALMCS in the first place, we would take the induced subgraph, satisfying the inductivity constraint mentioned in Section 2. Specifically, we the output assignment matrix T and check if node has a 1 in its corresponding row (for G1) or column (for G2) T to decide whether is selected in the predicted MCS.
Notice that by checking the size of the extracted subgraphs against the ground-truth MCS size (Equa- tion and 8 we allow equal-sized MCS results be evaluated correctly, since for many graph pairs there are more than one correct MCS result.
Here we give more insights behind the two metrics. The intuition behind the hard metric is that we only check whether the the extracted subgraphs are strictly equal to the size of the true MCS or not. However, this is too strict and does not reveal too much information about the model performance when the extracted subgraphs are not the same size as the true MCS. An easy measure would be to directly report on the predicted MCS size, but this does not take into account non-isomorphic subgraphs. The soft metric accounts for both these issues by checking the fraction of the predicted MCS size over the true MCS size only for isomorphic subgraphs. Notice that if the predicted MCS even larger than the true MCS, the C(.,)) function will return 0 because it is not possible for the subgrpahs to be both larger than the true MCS (generated by the exact solver McSPLIT) and isomorphic.
E RESULT ANALYSIS
In addition to Exact % and Soft metrics, we may also evaluate our model on the percentage of extracted subgraphs which are isomorphic (Iso %).
Following the same notation used to define Exact % and Soft %, we define Iso as follows:
ΣN C(Sa, N
Iso %
(9)
As seen in Table 2 NEURALMCS explicitly encodes the isomorphism constraint into the stopping condition. This is one reason why NEURALMCSS able to achieve high accuracy, especially in Soft % in Table Notice, phic when not isomorphic), as it is possible for differently structured graphs, with different node embeddings, to have the same subgraph embedding once all the node embeddings Because these situations are relatively rare (both graphs would need to have the same subgraph em- bedding to floating point precision), NEURALMCS is extract isomorphic subgraphs 100% of the
method does not guarantee exclusion of aossiioossisess (predicting isomor-
aggregated.
ssoo wm..pphhhiimcicmmmmmmmmmm... coul d___dd_ee______ be ismmorphic.
html
13

---

Under review as a conference paper at ICLR 2020
time the provided datasets. Our model does guarantee exclusion of false-negative negatives,, as, if two graphs are isomorphic, our embedding propagation methodology must produce the same subgraph embeddings.
Table 2: Iso % accuracy metric across four real graph datasets. All methods have been adapted for
the MCS detection task. Dataset descriptions and details can be found Appendix ^
Method
AIDS
LINUX
IMDB
REDDIT
MCSPLIT *
100.000
100.000
100.000
100.000
IMAGE- GMN
0.033
19.790
N/A
20.261
IMAGE-PCA
0.229
22.693
38.582
33.987
BASIC-GAT
80.039
82.269
99.365
73.856
BASIC-GMN
91.183
97.230
96.924
95.425
NEURALMCS
100.000
100.000
100.000
100.000
F ABLATION STUDY
We first form matching matrix then extract subgraph guided by this matrix. To form the matching matrix, we utilize representation learning to make node embeddings; compute using similarity scores from node embeddings (Section 3.T); compute Y through normalization of X (Section 3.1 To perform extraction, we utilize the GUIDED SUBGRAPH EXTRACTION method proposed (Sec- tion 3.3p.
We perform more in-depth ablation studies to show the importance of each component whose results are shown Table 3
Table Abaltion study results on AIDS. The numbers are the "Exact %" defined in Section 4.1
Subgraph Extraction Strategy
Matching Matrix Computation
GSE
Threshold
Threshold LSAP
GMN Our Normalization
98.525
(NEURALMCS)
25.795
17.076
GAT Our Normalization
98.525
26.057
17.339
DGCNN Our Normalization
96.657
22.091
13.045
GMN Sigmoid
97.083
10.521
12.488 (BASIC-GMN)
GMN Sinkhorn Softmax
60.439
12.488
0.197
F. ON THE IMPORTANCE GMN
GAT Our Normalization and DGCNN Our Normalization use GAT (Velickovic al.) 2018) and DGCNN (Wang et al. 2019b) used in Wang & Solomon 2019) respectively to perform node embeddings. Interestingly, when fed into our proposed GSE step. their exactly solved percentages are quite close to GMN, which is close to perfectly detecting the MCSs for all the testing pairs. Even with simpler thresholding based subgraph extraction strategies (see Section F3 below for details), their performances are still similar to (or even better than) GMN. This seems to suggest that the choice of node embedding methods does not appear to influence the performance much when our proposed GSE strategy is used.
should be noted that earlier we used simpler GSE strategy which always selected the node pair with the largest matching score in Y in during search fronticr expansion. This model did not check all the possible node pairs by sorting the node matching scores and iterate through these pairs for consideration of being selected in the MCS prediction. When tested this simpler GSE strategy, GMN indeed performed approximately 4.0% better than GAT and DGCNN.
In summary, the choice of node embedding representation methods does not influence the perfor- mance too much, and very good accuracy can be obtained when the proposed normalization and GSE methods are both used.
14

---

Under review as a conference paper at ICLR 2020
F.2 ON THE IMPORTANCE OF NORMALIZATION
GMN + Sigmoid (BASIC-GMN) uses sigmoid normalization each individual element of the X matrix, instead of our normalization scheme (Section 3.1 Equations [ and 2 to obtain Y. As sigmoid treats each node-node pair in Y as independent (an incorrect assumption), we that its performance worse than our proposed normalization scheme, especially when the threshold or threshold LSAP strategies are used. However, similar our findings in Section F.I when our proposed GSE strategy is used, GMN + Sigmoid performs only slightly worse than NEURALMCS, which further confirming the usefulness of the proposed normalization scheme and the GSE method.
GMN + Sinkhorn Softmax uses successive row- and column- softmax normalization (softmax to ensure that the matching matrix Y is in the range (0.1)) on the X matrix (similar to the Sinkhorn algorithm (Knight (2008) used in IMAGE-PCA for image matching Fi instead of our normalization scheme. As softmax does not explicitly allow nodes to go unmatched (Section B.I as dictated by the MCS definition, we see that our normalization procedure performs much better.
As mention in Section the assumptions made for image matching do not naturally transfer to and work well for the MCS detection task. In fact, with the simple element-wise sigmoid normalization on X, the performance is much better than the Sinkhorn normalization technique. The iterative row- and column- wise normalization on X is not good choice for the task of MCS where nodes can remain unmatched with low scores in the final Y.
F.3 ON THE IMPORTANCE OF GSE
For each Matching Matrix Computation method, we run 3 different subgraph extraction strategies: GSE, thresholding, and thresholding LSAP (Linear Sum Assignment Problem which the Hungarian algorithm (Kuhn 1955) to solve, described in AB]
For thresholding, for each of the two graphs, we select the nodes whose probabilities of being included in the MCS are greater than a tunable threshold, yielding two subgraphs. We calculate such probabilities by taking the summation of rows and columns of the matching matrix Y. More details can be found in Appendix
For thresholding LSAP, we ensure that the detected subgraphs are of equal size and have one-to- one node-node mapping (to validate their isomorphism) by running the Hungarian algorithm on the remaining rows and columns of Y after thresholding. We cannot run ISAP on the original Y since LSAP would select all nodes in the smaller of the two graphs.
Neither of these simpler subgraph extraction methods enforces the subgraph isomorphism constraint, which explains their worse performance compared with GSE.
We find that our major novelties (GSE and normalization technique) are the most important compo- nents in producing good performance.
G SCALABILITY STUDY
is trained on graph pairs with ground-truth MCS results, which can be either obtained by McSPLIT or the following way which provides cheap supervision without using any exact MCS solver. The high level idea of generating ground-truth MCS training pairs without exact MCS solver to create such pairs with smart design instead of computing MCS for any given pair of graphs. One possible way to create such pair is to extract an induced subgraph from a given graph, and the ground-truth MCS of the two graphs is naturally the extracted subgraph. More concretely, our experimental setup is as follows: We generate training graph pairs by first using the BarabsiAlbert model (Barabási & Albert 1999) to generate 1000 graphs of size 32. For each generated graph, We randomly extract one connected 16-node subgraph from it. Each generated graph and extracted subgraph form one pair, giving a total of 1000 training graph pairs (our training set). Notice, this generation procedure allows us to know the MCSs during generation.
IMAGG-PCA performs additional normalization and adopts slightly different Sinkhorn Layer for Linear Assignment which yields in similar performance to GMN + Sinkhorn Softmax indicated in Table T
15

---

Under review as a conference paper at ICLR 2020
We follow similar procedure for testing set, where the Barabsi-Albert model to generate 100 graphs of size 16, 32, 64, and 128 (denoted as "Test Dataset Size" in the table below). For each generated graph, we extract one connected 8-, 16-, 32-, and 64- node subgraph respectively. This gives us 5 test sets, each with 100 graph pairs.
We the following metrics for thorough evaluation:
1. Solved %: It measures the percentage of pairs that the model can successfully finish within 100 seconds.
2. Soft %: It measures the fraction of the predicted MCS size over the true MCS size for the isomorphic extracted subgraphs (Appendix D
3. Iso %: Among the pairs that can be solved within the time budget, measures the per-
centage of pairs whose extracted subgraphs are isomorphic. This is an important metric because subgraph isomorphism is a key constraint required by the definition of MCS.
4. Dev in # nodes: among the pairs that can be solved within the time budget, measures the average deviation of the number of nodes in the predicted MCS versus the number of nodes in the true MCS. The range of this metric is [0, N] where N is the number of nodes of the largest graph in a dataset. This metric gives more intuitive understanding of the performance of a model compared to "Soft %% since it reports the number of nodes directly.
5. (Average) Runtime (msec): It measures the average running time per testing pairs that the model solves within the time budget. other words, if model fails solving a pair within the time budget, the runtime will NOT be taken into account by this metric for fair comparison
We set the time budget to 100 seconds and 500 seconds for MCSPLIT respectively, and the results shown in Table 4
Table 4: Scalability study results on AIDS.
Test Dataset size
Metries
MCSPLIT (100s)
McSPLIT (500s)
MCSPLIT
Solved % Soft
100.000
100.000
100.000
100.000
100.000
99.625
16
Iso %
100,000
100.000
100.000
Dev in # nodes
0
0.030
Runtime (msec)
295.576
236.502
550.688
Solved %
100.000
100.000
100,000
Soft %
100.000
100.000
99.563
32
Iso %
100.000
100,000
100.000
Dev in # nodes
0
0.070
Runtime (msec)
333.793
340.310
787.901
Solved %
61.000
62,000
100,000
Soft %
61.000
62.000
98.843
64
Iso %
100.000
100.000
100,000
Dev # nodes
0
0.370
Runtime (msec)
4509.056
10351.813
940.581
Solved %
26.000
28.000
100,000
Soft %
26.000
28.000
75.484
128
Iso
100.000
100.000
100.000
Dev # nodes
0
15.690
Runtime (msec)
1220.117
18809.848
1194.089
NEURAL achieves performance close the exact ground truth solver in terms of accuracy, and scale to much larger graphs which the exact solver fails, most of the time, at solving within the time budget.
For accuracy, see that the size of MCS extracted for the model is often over 98% the true MCS size. Interestingly, for graphs of size 64, we find that the extracted subgraphs differ between our model and the true MCS only in less than node (0.37 nodes) on average. This indicates that our proposed method (NEURALMCS) can detect MCS that the current state of the art (MCSPLIT) cannot, due careful design and the incorporation of learning algorithms.
16

---

Under review as a conference paper at ICLR 2020
For running time, model is comparable to slower than the ground truth detector for simpler cases (j second) but much faster for larger graphs. This could be due to our model incurring overhead from Python implementation. while McSPLIT is implemented in C++. However, when the dataset size equals 128, MCSPLIT fails for most pairs, as the MCS problem is NP-hard, while NEURALMCS solve all the pairs due to guaranteed time complexity (Section 3.4.. Notice, there is no theoretical time complexity guarantee for McSPLIT (exponential time complexity in the worst case (McCreesh al. 2017)), resulting in significant average running time increase from 1220.1 msec to 18809.8 msec when only 2 additional pairs are solved by increasing the time budget from 100 seconds to 500 seconds. In fact, we observed that the actual running time of the branch-and- bound algorithm MCSPLIT strongly depends on the actual graph structures varying from graph to graph.
In summary, when graphs are larger and larger, MCSPI.T quickly becomes almost unusable in practice due to an inability to yield results most of the time, while NEURALMCS still extracts high- accuracy MCSs consistently and runs much faster than MCSPLIT with guaranteed theoretical time complexity. In practice, we observe that our model can run successfully on a 12-GB GPU until 4000-node graphs when the GPU runs out of memory, in which case McSPLIT almost surely cannot be used either.
H DISCUSSION ON SUBGRAPH ISOMORPHISM CHECKING OF GUIDED SUBGRAPH EXTRACTION
In the proposed GUIDED SUBGRAPH EXTRACTION (GSH) strategy (Section 3.3.1 we check if the inclusion of new node pair would result in two isomorphic subgraphs by checking if [|wn] - w22 is smaller than equal to a threshold, which is criteria that allows us to punish mismatched nodes more softly. While an iterative check would achieve efficiency benefits by avoiding computing the subgraph embeddings, it assumes every step have performed non-ambiguous matching. For example, suppose we have graphs, where in the current iteration of GSE, we have 2 fully connected 3-node subgraphs currently extracted with node-node mappings. We label the node ids of these 2 graphs as 1-2-3 and a-b-c respectively and the mappings as I-a, 2-b, 3-c. If we select a new node 4 from 9i and a new node dl from G2 and 4 is connected to 2 and d is connected a, iterative procedure would not be able to tell that the addition of node 4 and d to the MCS is valid (since 2-b is matched but NOT 2-a). Fundamentally, the structure for 1,2.3 and b, are similar, so it uncertain (and expected) that the computed node matchings would be 2-a, 1-b or 2-b, 1-a.
In contrast, our proposed checking strategy can account for the above- mentioned uncertainty by do- ing aggregation of node embeddings to obtain subgraph-level embeddings w1 and W2, since this does more (WI.) graph isomorphism test (Sher-) vashidze et al. 201T). In WI., each node in the two graphs is represented as an aggregation of local node features, and each graph is represented as an aggregation of node labels. The algorithm stops and decides two graphs are not isomorphic when the two graph-level node label sets are different. In our model, the graph-level node label set is equivalent wi and W2, and our GSE decides that the subgraphs are not isomorphic when the two graph-level representations are different enough.
not involve explicitly finding the node-node mappings. Instead, it checks the isomorphism principled way borrowing insights from Weisfeiler-Lehman
In conclusion, our proposed checking strategy addresses the ambiguous node mapping issue which the iterative isomorphism check could not solve, and is theoretically connected to the WI. algorithm for graph isomorphism test.
I DISCUSSION ON LEARNINING CAPACITY OF GUIDED SUBGRAPH EXTRACTION
In our current model, we form a matching matrix for both training and inference, and perform our loss function on the matching matrix during training (Section 3.2 and utilize GSE (Section 3.3 guided by the matching matrix during inference to extract subgraphs. We use GMN for node em- beddings (Section 2.2 and Section 3.1) and feed the matching matrix into GSE, which is fixed during the iterative GSE process. However, one potential issue is that once a node pair is selected, the ex- tracted subgraph grows by one node causing the candidate pairs change in the next iteration.
17

---

Under review as a conference paper at ICLR 2020
Ideally, node embeddings should be updated to reflect such change after each iteration. By introduc- ing learnable components to iteratively update the node embeddings to reflect such change, we can train the GSE component using guidance from the ground-truit node mappings in the MCS, making the training stage and inference stage consistent and match each other.
To accomplish this, propagate the node embeddings at each iteration of GSE with learnable weights to recompute the matching matrix Y such that the next iteration's node embeddings will be conditionally updated based the current extracted subgraph. To achieve it, extend GMN to update the node embeddings for the extracted subgraph at each GSE iteration. GMN updates the node embeddings of two graphs jointly by performing intra- and anter-graph message passing- Thus, one can directly apply GMN to the extracted subgraph at each GSE iteration, and calculate the loss function at the end of GSE process (replacing the current BCE loss on the matching matrix Y), achieving conditional node embeddings in the GSE step of the model.
In implementation, we make further modification to GMN by not propagating to matched nodes in the two extracted subgraphs. This is because want the node embeddings for the currently ex- tracted isomorphic subgraphs to stay as consistent as possible and not be influenced by any unpicked nodes in the larger graph or any nodes from the opposing graph.
We run both modified versions (with and without further modification) of NEURAL ALMCS on AIDS, and the performance increase is only marginal (< 1% increase). Therefore, by forgoing this step during training and only using GSE only during testing, we can gain a free speed up in training time.
J MORE CASE STUDY
All case study plots can be seen in Figure 5 input pairs, where adding any extra nodes would break the MCS constraints. In the LINUX, IMDB, and REDDIT dataset, we see examples where the graph structures are vastly different, yet NEU- RALMCS is still able correctly differentiate MCS nodes. In the AIDS dataset, we the model is able to successfully extract subgraphs which maintain node labels. In the IMDB dataset, we see the model can handle denser and larger size graphs.
We see that our model is able to differentiate difficult
18

---

Under review as a conference paper at ICLR 2020
(a) AIDS
(b) LINUX
(c) IMDB
(d) REDDIT
Figure 5: Case study.
19


Reviews:
[{"review_id": "Syl40jCRcH", "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 authors proposed a novel method to find the Maximum Common Subgraph (MCS) of two graphs. I am familiar with the quadratic assignment problem (QAP) based graph matching and I am not very familiar with the MCS problem. \n\nThe authors adopt Graph Matching Networks (GMN) for feature embedding, and then similarity matrix X can be generated by computing the similarities between the embeddings. The similarity matrix is then normalized using a similar way as the sinkhorn procedure in [1-3]. The Assignment matrix then can be given from X. Then a novel procedure, named Guided subgraph Extraction (GSE, which is considered as the main contribution of this paper), is used  to get an MCS from assignment matrix. Here the authors may consider a simple baseline, which is to use QAP to give the assignment matrix, and then run GSE to obtain the MCS. \n\nOverall the paper is well written, and the experiment is good and solid. \n\nSome suggestions:\nThe GCN based GMN might not be the best choice for graph embedding. The authors may consider stronger Graph Neural Networks such as DGCNN (used in [3]) or Message Passing Neural Network (used in [4] and [5]) as the graph embedding module in the future work. \n\n[1] Deep Learning of Graph Matching, CVPR18\n[2] Learning Combinatorial Embedding Networks for Deep Graph Matching. ICCV19\n[3] Deep Closest Point: Learning Representations for Point Cloud Registration. ICCV19\n[4] Deep Graphical Feature Learning for the Feature Matching Problem, ICCV19\n[5] Neural Message Passing for Quantum Chemistry, ICML17", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and 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": "H1xE5kL6Yr", "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": "This paper proposes a novel algorithm NeuralMCS for maximum common subgraph (MCS) identification. The proposed algorithm consists of two components. One is a neural-network model based on Graph Matching Networks (GMN, Li et al, 2019) to learn a node-to-node matching matrix from examples of the ground-truth MCS results. Another is the algorithm called GSE (Guided Subgraph Extraction) to obtain an MCS by making an explicit assignment from the estimated matching matrix by the NN model. Experimental comparisons are made to other NN-based approaches combined with threshold-based assignments by the Hungarian algorithm (w.r.t the accuracy) and to a state-of-the-art exact algorithm MCSplit, and show the effectiveness of NeuralMCS.\n\nThis paper proposes an interesting method for MCS detection which would have large application interests. Though the basic idea is nice,  the reported performance gains would be a bit less convincing due to the following evaluation problem and its weak novelty. \n\nThe algorithm has two parts, and the first NN part to learn a matching matrix is mostly based on the already existing algorithm of GMN (Li et al, 2019). The novel part would be primarily in post-processing normalization (described in 3.1) for the matching matrix and seems to also be applicable to other NNs (for example, GAT?). The second part GSE to get an explicit subgraph also seem to be applied independently to the first part. We can see that combining these two parts worked, but it is unclear how each component contributes to the performance gain compared to any possible alternatives of each part.\n\nI understand that MCS detection from a matching matrix (and node state vectors) is not exact if we just use Hungarian-like linear assignment problem (LAP) solvers for a submatrix obtained by a simple thresholding, but both post-processing normalization and GSE parts (which brings the novelty) can be more carefully evaluated through some 'ablation studies' using some simple alternative substitutes.", "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": "N/A"}, "extra_text": {}}, {"review_id": "B1xWJnUGiH", "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": "This paper proposed a graph net based approach for subgraph matching. The general idea is based on the graph matching network (Li et.al, ICML 2019) that computes the node embeddings of two graphs with co-attentions. The training requires the supervision of ground truth matching. During inference an iterative method with heuristic stopping criteria is used. Experiments on tiny graphs show better results than learning based baselines, but worse results than MCS solver.\n\nOverall the paper is well motivated. However there are several major concerns with the paper:\n\n1. Since it relies on the solver to provide training data, it might be hard to train on large graphs as there would be no cheap supervision. Also it seems that getting slightly faster but much worse results than the solver on small graphs is not that exciting. \n\n2. It seems there's a mismatch between training and inference. The inference method is done iteratively, where the Eq (6) is somewhat not clear to me: as this ||w1-w2|| criteria is not trained during training, it seems quite heuristic by doing so. \n\n3. I’m not sure why the two stop conditions are needed. One can easily check (incrementally) whether the added nodes are isomorphic.  \n\n4. The graphs used in experiments are too small. \n\nSome other minor issues:\n\nIt would be better to define Y with Eq (1) and Eq (2) in the paper. There seems to be no explicit definition of Y. \n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed graph neural networks based approach for subgraph detection. The reviewers find that the overall the paper is interesting, however further improvements are needed to meet ICLR standard: 
1. Experiments on larger graph. Slight speedup in small graphs are less exciting.  
2. It seems there's a mismatch between training and inference. 
3. The stopping criterion is quite heuristic. 

Decision: Reject