Learning to Search for Fast Maximum Common Subgraph Detection
Authors: Yunsheng Bai
Derek Qiang Xu
Yizhou Sun
Wei Wang
Venue:  (2021)
Keywords: graph matching
maximum common subgraph
graph neural network
reinforcement learning
search

Abstract: Detecting the Maximum Common Subgraph (MCS) between two input graphs is fundamental for applications in biomedical analysis, malware detection, cloud computing, etc. This is especially important in the task of drug design, where the successful extraction of common substructures in compounds can reduce the number of experiments needed to be conducted by humans. However, MCS computation is NP-hard, and state-of-the-art MCS solvers rely on heuristics in search which in practice cannot find good solution for large graph pairs under a limited search budget. Here we propose GLSearch, a Graph Neural Network based model for MCS detection, which learns to search. Our model uses a state-of-the-art branch and bound algorithm as the backbone search algorithm to extract subgraphs by selecting one node pair at a time. In order to make better node selection decision at each step, we replace the node selection heuristics with a novel task-specific Deep Q-Network (DQN), allowing the search process to find larger common subgraphs faster. To enhance the training of DQN, we leverage the search process to provide supervision in a pre-training stage and guide our agent during an imitation learning stage. Therefore, our framework allows search and reinforcement learning to mutually benefit each other. Experiments on synthetic and real-world large graph pairs demonstrate that our model outperforms state-of-the-art MCS solvers and neural graph matching network models.

Under review as a conference paper at ICLR 2021
LEARNING TO SEARCH FOR FAST MAXIMUM COM- MON SUBGRAPH DETECTION
Anonymous authors Paper under double-blind review
ABSTRACT
Detecting the Maximum Common Subgraph (MCS) between two input graphs is fundamental for applications in biomedical analysis, malware detection, cloud computing, etc. This is especially important in the task of drug design, where the successful extraction of common substructures in compounds can reduce the number of experiments needed to be conducted by humans. However, MCS computation NP-hard, and state-of-the-ar MCS solvers rely on heuristics in search which in practice cannot find good solution for large graph pairs under limited search budget. Here we propose GLSEARCH, a Graph Neural Network based model for MCS detection, which learns to search. Our model uses state-of- the-art branch and bound algorithm as the backbone search algorithm to extract subgraphs by selecting one node pair time. In order to make better node selection decision at each step. we replace the node selection heuristics with a novel task-specific Deep Q-Network (DQN), allowing the search process find larger common subgraphs faster. To enhance the training of DQN, we leverage the search process to provide supervision in a pre-training stage and guide our agent during an imitation learning stage. Therefore, our framework allows search and reinforcement learning to mutually benefit each other. Experiments on synthetic and real-world large graph pairs demonstrate that our model outperforms state-of- the-art MCS solvers and neural graph matching network models.
INTRODUCTION
Due to the flexible and expressive nature of graphs, designing machine learning approaches to solve graph tasks is gaining increasing attention from researchers. Among various graph tasks detecting the largest subgraph that is commonly present in both input graphs, known as Maximum Common Subgraph (MCS) (Bunke & Shearer, 1998) (as shown in Figure Tp. is an important yet particularly hard task. MCS naturally encodes the degree of similarity between two graphs, is comainn-ggosiio and thus has occurred in many domains such as software analysis (Park al. (201)), graph database systems (Yan et al. 2005) and cloud computing platforms (Cao et al. [201] In drug design, the manual testing of the effects of new drug is known to be major bottleneck, and the identification of compounds that share common or similar subgraphs which tend to have similar properties can effectively reduce the manual labor (Ehrlich & Rarey 2011).
MCS detection is NP-hard in its nature and is thus very challenging task. On one hand, the state-of- the-art exact MCS detection algorithms based on branch and bound run in exponential time in worst cases (Liu et al. ) What is worse, they rely on several heuristics on how to explore the search space. For example, MCSP (McCreesh et al. 2017) uses node degree as its heuristic by choosing high-degree nodes to visit first, but in many cases the true MCS contains small-degree nodes. On the other hand, existing machine learning approaches to graph matching such as Wang et al. (2019) and Bai al. (2020b) either do not address the MCS detection task directly or rely on labeled data requiring the pre-computation of MCS results by running exact solvers.
In this paper, present GLSEARCH (Graph Learning to Search), general framework for MCS detection combining the advantages of search and reinforcement learning. GLSEARCH learns to search by adopting Deep Q-Network (DQN) (Mnih et al. 2015) to replace the node selection heuristics required by state-of-the-an MCS solvers, leading to faster arrival of the optimal solution for an input graph pair, which is particularly useful when the simpler heuristics fail and graphs are large

---

Under review as a conference paper at ICLR 2021
D1
G₁
G2
G
Figure 1: Left: For graph pair (91, 92) with node labels, the induced connected MCS is the five- member ring structure highlighted in circle. Right: At this step. there are two nodes currently selected. According whether each node is connected the two selected nodes not, the nodes not in the current solution are split into three bidomains (Section (.2). denoted as "00", "01", and "10", where "0" indicates not connected For example, each node in the "10" bidomain is connected to the top "C" node in the subgraph and disconnected the bottom "C" node in the subgraph.
node in the selected nodes, and "1" indicates connected.
with a limited search budget. Thanks to the learning capacity of Graph Neural Networks (GNN), our DQN is specially designed for the MCS detection task with novel reformulation of DQN to better capture the effect of different node selections. Given the large action space incurred by large graph pairs, to enhance the training of DQN, we leverage the search algorithm to not only provide supervised signals in pre-training stage but also offer guidance during imitation learning stage.
Experiments on real graph datasets that are significantly larger than exisitng datasets adopted by state-of- of- the-art MCS solvers demonstrate that GLSEARCH outperforms baseline solvers and machine learning models for graph matching in terms of effectiveness by large margin. Our contributions be summarized follows:
We address the challenging yet important task of Maximum Common Subgraph detection for gemeral-domain input graph pairs and propose GLAEAACH as the solution.
The key novelty is the DQN which learns search. Specifically, it is trained under the reinforcement learning framework to make the best decision at each search step in order quickly find the best MCS solution during search. The search in turns helps training of DQN in a pre-training stage and an imitation learning stage.
We conduct extensive experiments on medium vidium--sze synthetic graphs and very large real- world graphs demonstrate the effectiveness of the proposed approach compared against series of string baselines in MCS detection and graph matching.
2 PRELIMINARIES
2.1 PROBLEM DEFINITION
We denote graph = (V,E) where V and E denote the vertex and edge set. An induced subgraph is defined as G. = (V., &.) where E, preserves all the edges between nodes in Vs, i.e. Vi,j E V., (i, E E, if and only if (i. E. In this paper, we aim at detecting the Maximum Common induced Subgraph (MCS) between an input graph pair, denoted as MCS(G1, G2), which is the largest induced subgraph that contained in both G1 and G2. In addition, we require MCS(GI,9) to be connected subgraph. We allow the nodes of input graphs to be labeled, in which case the labels of nodes in the MCS must match as Figure [ Graph isomorphism and subgraph isomorphism can be regarded as two special tasks of MCS: IMCS(G1, G2) [il = [V2] if G1 are isomorphic to Gz. |MCS(91, (2) = min (IV (2 when Gn (or G2) is subgraph isomorphic to G2 (or G1).
2.2 SEARCH ALGORITHM FOR MCS
Among various algorithms for MCS, adopt the tfth--tfthheart search-based algorithm in framework. The basic version, MCSP, is presented in McCreesh et al. (2017) and the more advanced version, MCSP+RL, is proposed in Liu et al. (2019). The whole search algorithm, outlined in
2

---

Under review as a conference paper at ICLR 2021
Algorithm| [|] is branch- saanch-and-bound algorithm that maintains a best solution found so far throughout
the search, which is initialized as empty subgraphs. In each search iteration, denote the current search state st consisting of G1 92, the current selected subgraphs 91, (Vis: Eis) and G2. as well as their node-node mappings. The algorithm tries to select one node pair, (#;, U2); where o; is from 91 and Vi is from G2. as its action, denoted as de, and either backtracks to the parent search state if the solution is not promising or continues the search otherwise. Various heuristics on node pair selection policy, denoted as "policy", ,, are proposed in MCSP and McSP+RL. For example, in MCSP, nodes of large degrees are selected before small-degree nodes.
(V2s. Egs) )
There are two major limitations of McSP and McSP+RL: (1) Such heuristics- couristics-based node pair selection policy cannot adapt to different graph structure (2) The search may enter bad state and get "stuck" without finding a better (larger) solution, maxSol, for many iterations.
Algorithm 1 Branch and Bound for MCS
1: Input: Input graph pair G1, G2.
2: Output: marSol.
3: Initialize stack <- new Stack().
At each search state, order to compute the upper bound "UB," and reduce the action space
4: Initialize max:ol <- empty solution.
5: stack.push( (so):
"Ai", i.. the candidate node pairs to select from, the concept of "bidomain" is introduced. Bido-
6:
while stack & do
7:
8t 5 staack.pop():
mains partition the nodes in the remaining sub- graphs, i.e. outside 91s and G2s, into equivalent classes. Among all bidomains of a given state, D. the k-th bidomain DR consists of two sets of nodes, (Vh1 V/22) where V/, and V/2 have the same connectivity pattern with respect the already matched nodes V1. and V2,- Figure I shows an example with three bidomains. Due to the subgraph isomorphism constraint posed by MCS, only nodes in Vi can match to 1222 and vice versa. This also guarantees the extracted subgraphs at each state are isomorphic to each
8:
curSol t- Selget(Curoo((::
9:
if JcurSol| > mmaxSol| then
10: mar:Sol +- curSol;
end if
12:
UB, + Sol + overestimate(s:))
13:
if UB; S |mazSol| then
14:
continue;
15:
end if
16:
A, s,.actions;
17:
0t + po,
18:
scactiooss t- s,,actions May):
19:
stack.push(ss);
other. Thus, each bidomain can contribute at most min((V% ())))))) nodes to the future best
20:
St+1 f enw.update(s; Ad;;
21:
stack.push($1:))
solution. Therefore, the upper bound can be esti-
22:
end while
mated as ΣDYED min((Va (2)a)). This upper
bound computation is consistently used for all
the methods in the paper. The major difference is in the policy for node pair selection.
3 PROPOSED METHOD
In this section we formulate the problem of MCS detection as learning an RL agent that iteratively grows the extracted subgraphs by adding new node pairs to the current subgraphs in graph- structure-aware environment. We first describe the environment setup, then depict our proposed Deep Q-Network (DQN) which provides actions for agent to grow the subgraphs in a search context. We also describe how to leverage supervised data via pre-training and imitation learning.
3.1 LEVERAGING DQN FOR SEARCH
Since graph matching for MCS detection must satisfy a hard constraint that the resulting two subgraphs must be isomorphic to each other, instead of learning to match two graphs in one shot, we design an RL agent which explores the input graph pair and sequentially grows the extracted two subgraphs one node pair at time. The iterative subgraph extraction process can be described by
'The original algorithm is recursive. To highlight our novelty, we rewrite into an equivalent iterative version. 2 *MCSP+RL claims uses reinforcement learning (RL) to compute a score for each node pair. However, the scores for each node are the only learnable parameters, whose update relies on heuristic. This requires the learning of scores for each new testing graph pair. In contrast, we use continuous embeddings to represent graphs which are fed into DQN to compute score trained on many graph pairs. Once trained, GEACH be applicd to any new testing pair without retraining.
3

---

Under review as a conference paper at ICLR 2021
10
18
Root
Pruned by branch and bound
14
19
Terminal
Subgraph Growth
Predicted MCS
20
15
Figure An illustration of the search process for MCS detection. For (91, 92), the branch and bound search algorithm (Section2) 2n2 and Algorithm yields tree structure where each node represents one state (st) with id reflecting the order in which states are visited, and each edge represents an action (a,) of selecting one more node pair. The search is essentially depth- septh-first with pruning by the upper bound check. Our model learns the node pair selection strategy, i.e. which state to visit first. state 6 can be visited before state 1, a large solution can be found in less iterations. When the search completes or a pre-defined search iteration budget is used up, the best solution (output subgraphs) will be returned, corresponding to state 13 (and 14).
Markov Decision Process (MDP), where the definitions of state and action are the same as Section 2.2 The difference is that, for MDP, reward needs to be defined too. for MCS, the immediate reward for transitioning from one state to any next state rt = +1 since one new node pair is selected.
To address the issue that the algorithm may get stuck in bad state for many iterations without finding a larger solution, we utilize additional information stored in Q-values computed by our learned model. We suppose backtracking to earlier better state alleviate such issue in practice, but there lacks a principled measure for MCSP and McSP+RL to determine which earlier state better. By design, node pair selection policy is learned DQN, so agent knows only the quality of immediate actions, but also the values associated with previous states. Therefore, if the best solution found so far does not increase, i.c. we do not enter line 10 of Algorithm [ a pre-defined number of iterations, in the next iteration, we find the best state as determined by the Bellman Equation, remove that state, then visit it on line We refer this improved search methodology as promise-based search. More details can be found in the supplementary material.
3.2 REPRESENTATION LEARNING FOR DQN
Since the action space can be large for MCS, we leverage the representation learning capacity of continuous representations for DQN design. At state šr, for each action de, DQN predicts Q(t,, (t) representing the future reward to go the action de = (i.j) where i V1 and j E V/2 is selected, intuitively corresponding to the largest number of nodes that will be eventually selected starting from the action edge (St. 0.) as in tree in Figure 2
Based on the above insights, one design simple DQN leveraging the representation learning power of Graph Neural Networks (GNN) such as Kipf & Welling (0066) and Velickovic et al. (008))
by passing G1 and G2 GNN to obtain embedding per node, (h, vi Vi and (h,) Vj E D2). Denote CONCAT as concatenation, READOUT as a readout operation that aggregates node-level embeddings into subgraph embeddings h2 and h41, and whole-graph embeddings hG, and hGg state can then be represented as ht, CONCAT(hg,, ltg.; hat, h22). An action can be represented as ha, CONCAT(h,, h,). The Q function can the be designed as:
Q(5t, a4) = MI.P ML.PCCONCAT(h... ha,)) = MLP(CONNAA((ss, hsg h.1 h22, hi)))
(1)
However, there are several flaws to this simple design of Q function:
(A) h; and h generated by typical GNNs encode only local neighborhood information. but Q(s,, a+) represents the long-term effect of adding (i.j). What is worse, different node pairs have different embeddings, but their immediate rewards always +1 in MCS.
4

---

For the pre-training stage, we first observe the overall mse loss is - )²))² where yr the target for iteration and Q(st, ar) is the predicted Q(st, ae). We then notice that for small training graph pairs, the complete exploration of search space can be performed to obtain the true target for Under review as a conference paper at ICLR 2021
(B) Swapping the order of (1 and G2 should not cause (ss,, az) change, but concatenating embeddings from the two graphs causes the DQN to be sensitive to their ordering.
(C) How effectively leverage the node-node mappings between G1s and G2s for predicting (t; (z) remains a challenge.
To address these issues, we propose the following improvements over the simple DQN design.
Factoring out Action In order to maximally reflect the effect of adding node pair (i.j) to 91. and G2.. we first notice that Q* a.) Tt + (s++1) = 1 + VV* in MCS, where Q and V are the Q and value functions, respectively, and 7 the discount factor. Then, in order to compute the effect of de, we can compute the value associated with 81+11 which does not depend on a, and avoids the use of local h; and hj.
Interaction between Input Graphs To resolve the graph symmetry issue, we first construct the interaction between the embeddings from two graphs, i.c. INTERACT(h,11 h22), where h21 and h22 represent any embedding from 91 and G2 respectively and INTERACT(-) is any commutative function to combine the two embeddings (e.g. summation). This interacted embedding is later concatenated with other useful representations and fed into final MLP to compute the Q score. We describe our INTERACT() (.) operator in Section B.3
Bidomain Representations Bidomains derived from node-node mappings and partition the rest of 9 and 22 which is a more useful signal for predicting the future reward. In fact, as described in Section 2.2 bidomains have been adopted to in search-based MCS solvers to estimate the upper bound. Here, we require the harder prediction of ((5,, a²) for which we propose to use the representation of bidomains. Denote Dr as the representation for bidomain Dg. Similar to computing the graph-level and subgraph- embeddings, we compute D as
hD INTERACT(READOUTTT (h.li V)J),, READOUT((hyli V(2))).
Since we require the MCS to be connected subgraphs, we differentiate bidomains Die) that are connected (adjacent) to G1. and Go. from the single bidomain Dn disconnected (unconnected) from G1s and G2e (c.g. bidomain "00" in Figure J.. Given all the bidomain embeddings, we compute a single representation for ((()) hDD = READOUT( (hD, ( E D). Our final DQN has the form:
( a.) = 1 1 TMLP (CONCAT (INTERACT hg,)
hg,), INTERACT(ha,, h.2), hDD: hDo)). (3)
3.3 LEVERAGING SEARCH FOR DQN TRAINING
At each state st. the action space size in the worst case is quadratic to the number of nodes in the remaining subgraphs. Thus, to enhance the training of our DQN, before the standard training of DQN (Mnih et al. 2013), we pre-train DQN and guide its exploration with expert trajectories supplied by the search algorithm.
every (st.ag) by finding the longest sequence starting from s; to a leaf node in the search tree.
For larger graph pairs though, finding the true target becomes too slow. In that case, after pre-training, we enter the imitation learning stage where we let the agent mimic the decision made by the state-of- the-art MCS search algorithm instead of relying on its own predicted Q(st, az). More details can be in found in the supplementary material.
EXPERIMENTS
We evaluate GLSEARCH against two state-of-the-art exact MCS detection algorithms and series of approximate graph matching methods from various domains. We conduct experiments on a variety of medium-sized synthetic graph datasets and real-world graph datasets, whose details can be found in the supplementary material. Among the different baseline models, we find no consistent trend. This indicates the difficulty of our task, existing methods can not find a consistent policy that guarantees good performance on datasets from different domains. Our model can substantially outperform the baselines, highlighting the significance of our contributions to learning for search.
5

---

Under review as a conference paper at ICLR 2021
Table 1: Results on small and medium graphs. Each synthetic dataset consists of 50 randomly generated pairs labeled as "(generation algorith))- of nodes in each graph)".. "BA", "ER" and "WS" refer to the Barebasi-Albert (BA) (Barabási & Albert 1999), the Erdós-Rényí (ER) (Gilbert 1959). and the Watts-Strogatz (WS) (Watts& & Strogatz 1998) algorithms, respectively. N9 consists of 100 chemical compound graph pairs whose average graph size is 73. We show the ratio of the (average) size of the subgraphs found by each method with respect to the best result on that
dataset.
Method
BA-50
BA-100
ER-50
ER-100
WS-50
WS-100
NC1109
McSP
0,913
0.892
0.842
0.896
0.905
0.856
0.948
MCSP+RL
0.923
0.857
0,844
0.877
0.913
0.875
0.948
GW-QAP
0.945
0.887
0.855
0.925
0.916
0.898
0.966
I-PCA
0.899
0.863
0.848
0.923
0.879
0.852
0.951
NBURALMCS
0,908
0.889
0.846
0,906
0.889
0.865
0.954
GLSEARCH-
0.995
0.987
0,920
0,978
0,967
0.931
0,989
GLSEARCH
1.000
1.000
1.000
1.000
1.000
1.000
1.000
BEST SOLUTION SIZE
19.12
34.38
26.56
37.64
29.48
55.56
10.48
4.1
BASELINE METHODS
There are two groups of methods: Exact MCS algorithms including MCSP (McCreesh al. 2017)
and McSP+RL (Liu et al. 2019)) learning based graph matching models including GW-QAP (Xu
al. 2019a).
I-PCA (Wang et 2019), and NEURALMcS (Bai et al. 2020b).
All the methods either originally use or are adapted to use the branch and bound search framework in Section 2.2 with differences in node pair selection policy and training strategies. GW-QAP performs
Gromov- Wasserstein discrepancy (Peyré et al. (0166) based optimization for each graph pair and outputs matching matrix Y for all node pairs indicating the likelihood of matching which is treated the same way our g scores, i.e. at each search iteration index into Y to select a node pair. I-PCA and NEURALMCS also output a matching matrix but require supervised training, and thus are trained using the same training data graph pairs our GLSEARCH but with different loss functions and training signals. More details on training and setup of baselines can be found in the supplementary material. During testing, we apply the trained model all testing graph pairs. For medium-size synthetic testing graph pairs, each method is given a budget of 500 search iterations. For large real-world graph pairs, each method is given budget of 7500 search iterations. These budgets were chosen based on when the models' performances stabilized. Details about performance using other iteration budgets may be found in the Supplementary Material.
To validate the usefulness of the learned DQN, we compare GLSEARCH, our full model, with randomly initialized model, GLSEARCH-RAND which replaces the output of our DQN with a completely random scalar. We show the performance gain of our model through training by substantially outperforming this baseline on all real-world datasets.
4.2 PARAMETER SETTINGS
For I-PCA, NEURALMCS and GLSEARCH, utilize 3 layers of Graph Attention Networks (GAT) (Velickovic et al. 2018) each with 64 dimensions for the embeddings. The initial node embed- ding is encoded using the local degree profile (Cai & Wangl 2018). We use ELU(x) a(cxp(z)-1) for x < 0 and æ for x > 0 as our activation function where a T. We run all experiments with Intel 17-6800K CPU and one Nvidia Titan GPU. For DQN, we use MLP layers to project concatenated embeddings to a scalar. We use SUM followed by an MLP for READOUT and 1 IDCON followed by an MLP for INTERACT. For training, we set the learning rate to 0.001, the number of training iterations to 10000, and use the Adam optimizer (Kingma & Ba 2015). The models were implemented with the Py PyTorch and PyTorch Geometric libraries (Fey & Lenssen 2019).
4.3 RESULTS
The key property of GLSEARCH is its ability to find the best solution in the fewest number of search iterations. As shown in Table [ our model outperforms baselines in terms of size of extracted subgraphs on all medium-sized synthetic graph datasets and the small chemical compound dataset

---

Under review as a conference paper at ICLR 2021
Table Results on real-world large graph pairs. Each dataset consists one large real graph pair
(91, G2 may not be isomorphic, but G1s, G2. are isomorphic guaranteed by search). Below each
indicate these pairs are significantly larger than the ones in Table [ Consistent with Table we show the ratio of the subgraph sizes.
dataset name, we show its size min ( [
ROAD
DBEN
DBZH
DBPD
ENRO
CoPR
CIRC
HPPI
Method
652
1945
1907
1907
3369
3518
4275
2152
MCSP
0.374
0.815
0.797
0.722
0.694
0.684
0.498
0.864
McSP+RL
0.771
0.699
0.589
0.434
0.742
0.674
0.583
0.787
GW-QAP
0.305
0.929
0.855
0.808
0.711
0.860
0.354
0.834
1-PCA
0.267
0.551
0,589
0.607
0.650
0.707
0,203
0.762
NEURALMCS
0.977
0.785
0.616
0.620
0.737
0.742
0.561
0.785
GLSEARCH-RAND
0.641
0.762
0.658
0.639
0.814
0.755
0.603
0.814
GLSEARCH
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
BEST SOLUTION SIZE
131
508
482
521
543
791
3515
404
09. However, baseline solvers are already quite powerful on these datasets. As it is easy to extract the maximum common subgraph smaller graph datasets because the total search space grows exponentially with graph size, to truly show the performance advantage GLSEARCH, we also experiments large real-world graph datasets with thousands of nodes.
As shown Table T0 our model outperforms baselines in terms of the size of the extracted subgraphs on all large real-world datasets. The exact solvers rely heuristics for node selection, and consistently find smaller subgraphs compared to our results. Figure Satree@compreee results by MCSP and GLSEARCH. Since MCSP selects nodes with large degrees as heuristic, the selected nodes tend be confined in one dense cluster of large degree nodes in G1. This implies the subgraph in G2 matched to this dense cluster must also be dense (isomorphism constraint of MCS). In contrast, GLSEARCH is able to find long chains in 91 which allows easier matching in G2. In general, there are many cases of large weal-world graph pairs where heuristics are not enough to extract large high quality subgraphs. Due to its leveraging both learning and search, GLSEARCH consistently finds subgraphs more than double the size of those found by search based baselines for large real-world graph pairs.
(a) McSP
(b) GLSEARCH
Figure 3: Visualization of MCS results ROAD. Nodes with large degrees have large circles. For each method, we show the two graphs being matched. Selected subgraphs are colored in green.
Compared with learning based graph matching models, GLSEARCH is the only model which learns reward that dependent on both state and action, i.c. Q(st, az). GW-QAP, I-PCA, and NEURALMCSS essentially pre-compute the matching scores for all the node pairs in the input graphs, and therefore at each search step, the scores cannot adapt to the particular state, i.e. the matching scores only depend on G1, Gz- Notice state representation includes G1, G2 as well, hence GLSEARCH has more representational power than baselines. Trained under a reinforcement learning framework guided by search, GL.EAACHH also performs the best among learning based baselines.
7

---

Under review as a conference paper at ICLR 2021
Table Abaltion study on real datasets.
Method
ROAD
DBEN
DBZH
DBPD
ENRO
COPR
CIRC
HPPI
GLSEARCH (no hg)
0.977
0.878
0.925
0.845
0.860
0.987
0.980
0.960
GL.EEARC (no hg)
1.000
0.874
0.894
0.869
0.928
1.000
0.801
0.913
GLSEARCH (no hDD))
0.803
0.780
0.687
0.818
0.740
0.804
0.505
0.849
GLSEARCH (no (un))
0.576
0.856
0.782
0.768
0.823
0.932
0.323
0.938
GLSSARRC (SUM interact)
0.902
0.913
0.966
0.885
0.899
0.957
1.000
0.948
GLSEARCH (unfactored)
0,447
0.807
0.712
0,582
0.816
0.816
0,512
0.861
GLSEARCH (unfactored-i)
0,500
0.789
0.741
0.772
0.748
0.825
0.902
0.864
GLSEARCH
0.992
1.000
1.000
1.000
1.000
0.990
0.881
L.000
BEST SOLUTION SIZE
132
508
482
521
543
799
3989
404
4.4 ABLATION AND PARAMETER STUDY
To evaluate the effectiveness of different components proposed in our DQN model, we run ablation studies on all real world datasets.
We first measure the importance of each embedding vector fed to our DQN module, as described by Equation 3 We remove each embedding vector (specifically: hg INTERACT(hg, hgg)), h. = INTERACT (C.(1 h22)). hDc., and hupo) individually from the DQN model and retrain the model under the same training settings. Table 3 is consistent with our conclusion that every embedding vector used by GL.EEARCH is critical in capturing the search state's 's representation. Furthermore, we find leveraging bidomain representations is very beneficial to our model.
We next measure the importance of interaction to address the symmetry issue of the MCS calculation, where input graph pairs must be order insensitive. We first test the necessity of using more complex interaction functions, by replacing our IDCONV+MAXPOOL interaction with simple SUM for interac- tion (still followed by an MLP). As shown in Table 3 not be powerful enough to encode the interaction between 2 graphs. Particularly, this suggests that interaction is quite important to model performance.
we see that simpler interaction functions may
Finally, we measure the importance of factoring out actions from DQN model. We test this with 2 models. The first utilizes Equation [ to encode the Q-value, which we refer to as GLSEARCH (unfactored). Since Equation also suffers from the issue of graph symmetry, adapt this model to use the same interaction function as GLSEARCH to construct 3 order-invariant embeddings hg INTERACT(ha) and pass to the final MLP layer in Equation I We refer to this model as GLSEARCH (unfactored-i). Our results show that without factoring out the action, our performance comparable to or worse than MCSP, indicating the significant performance boost introduced by maximally reflecting the effect of adding node pairs.
hgg)). h. INTERACT(h,.. h.2). h. INTER (C,, hy) to concatenate
4.5 OVERHEAD OF GLSEARCII
Although in each iteration, GLSEARCH needs to compute a Q score, and is thus more computationally expensive than MCSP and McSP+RL, the decision GLSEARCH makes is "smarter" so that across many iterations, GLSEARCH can find a larger solution. In order to verify this, for each method, in each search iteration, we collect the best solution (largest subgraph) found far, and plot the best solution size across search iterations. Since we also measure the running time at each iteration, we also plot the best solution size across running time.
As shown in Figure 4. across the search. initially GLSEARCH finds a smaller solution compared to some baseline methods, but, with more iterations and running time, GLSEAACH quickly outperforms more and more baselines, eventually becoming the best method. Since all the methods follow the same search framework, and the only difference is the node pair selection policy, this experiment verifies that our learned policy can indeed find larger common subgraph. Given infinite amount of time budget, all the methods would find the true MCS which is the same or larger than the current best solution, but the aim of this section is to show the advantage of the learned policy for search allows the finding of a better solution in fewer iterations and running time. Section shows the plots on other datasets and provides additional experimental results.
8

---

Under review as a conference paper at ICLR 2021
340
Stee Salutoon Fourdd So
100
Stae tratt Solutron round
20
G0
8
P:50
X:50
20-
VcSp-ft
C1 land
Scsp-lt SW-k
Cloaarch-ladd
+ CLooach
Cloeacch
2
600
1000
2000
2000
4,00
5000
6000
7000
(a) Best solution size across time.
(b) Best solution size across search iterations.
Figure 4: Comparison of the best solution sizes of different methods ROAD.
5
RELATED WORK
MCS detection is HP-hard, with existing methods based constraint programming (Vismara & McCreesh et al.) (2016), branch and bound (McCreesh et al. 2017] Liu et al.) 2019).
Valery 2008
mathematical programming (Bahiense et al.) 2012), conversion to maximum clique detection (Levi 1973 McCreesh et al. 2016). etc. Closed related to MCS detection is Graph Edit Distance (GED)
computation (Bunke 1983, which in the most general form refers to finding series of edit operations that transform one graph to another and has also been adopted in many task where the matching or similarity between graphs is necessary. There approaches to approximate graph matching and similarity score computation, but these works either do not address MCS detection specifically and must be adapted Zanfir & Sminchisescul (2018); Wang et al.] (2019); | Yu et al. (2020); Xuu et al. (2019b a); Bai et al. (2019) 2020a)) Li et al. (2019) Ling et al. (2020), or rely on large amount of labeled MCS instances Bai et al. (202bb)
growing trend of using machine learning
6 CONCLUSION
We believe the interaction of search and learning is promising direction for future research, and take step towards bridging the gap by tackling the NP-hard challenging task. Maximum Common Subgraph detection. We have proposed reinforcement learning method which unifies search and deep Q-learning into a single framework. By using the search to train our carefully designed DQN, the DQN provides better node selection policy for search to find large common subgraph solutions faster, which is experimentally verified on real-world large graph pairs. In future, the adaptation of our framework to other NP-hard tasks requiring search can be explored.
REFERENCES
Monica Agrawal, Marinka Zitnik, Jure Leskovec, et Large-scale analysis of disease pathways in the human interactome. In PSB, pp. 111-122. World Scientific, 2018.
Laura Bahiense, Gordana Manić, Breno Piva, and Cid C De Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, 160( (1)1:))5223-241 2012.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. WSDM, 2019.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning based efficient graph similarity computation via multi-scale convolutional set matching. AAAI, 2020a.
Yunsheng Bai, Derek Xu, Ken Gu, Xueqing Wu, Agustin Marinovic, Christopher Ro, Yizhou Sun, and Wei Wang. Neural maximum common subgraph detection with guided subgraph extraction, 2020b. URL htt.htttsss///eeeeeee wttp:eeeeeeiieeeeeeeeeeeeeee www.::wwwwweeoeeeee/e//ee wtt.:oorowwooooooow/weheeoo..

---

Under review as a conference paper at ICLR 2021
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-51) 1999.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In ICML, pp. 41-48, 2009.
Horst Bunke. What the distance between graphs. Bulletin of the EATCS, 20:35-39, 1983.
Horst Bunke and Kim Shearer. A graph distance metric based on the maximal common subgraph. Pattern recognition letters, 19(3-4):255255)) 1998.
Chen Cai and Yusu Wang. A simple yet effective baseline for non-attributed graph classification. arXiv preprint arXiv: 181 1.00000,, 2018.
Ning Cao, Zhenyu Yang, Cong Wang, Kui Ren, and Wenjing Lou. Privacy-preserve query over enerypted graph-structure data in cloud computing. In 2011 31st International Conference Distributed Computing Systems, pp. 393-402 402. IEEE, 2011.
Asim Kumar Debnath, Rosa I. Lopez de Compadre, Gargi Debnath, Alan Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroarromaiic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
Hans- Chus--Cristtin Ehrlich and Matthias Rarey. Maximum common subgraph isomorphism algorithms and their applications in molecular science: review. Wiley Interdisciplinary Reviews: Computa- tional Molecular Science, 1(1):68-79 79, 2011.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Edgar N Gilbert. Random graphs. The Annals of Mathematical Statistics, 30(4): 1959.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2016.
Bryan Klimt and Yiming Yang. Introducing the enron corpus. In CEAS, 2004.
Der-Tsai Lee and Bruce Schachter. Two algorithms for constructing delaunay triangulation. International Journal of Computer Information Sciences, 9(3):119-22) 242, 1980.
Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6( 6(1):29-123, 2009.
Giorgio Levi. A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo, 944:344, 1973.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. ICML, 2019.
Xiang Ling, Lingfei Wu, Saizhuo Wang, Tengfei Ma, Fangli Xu, Chunming Wu, and Shouling Ji. Hierarchical graph matching networks for deep graph similarity learning, 2020. URL https
//openreview net oott://roumii
Yan-li Liu, Chu-min Li, Hua Jiang, and Kun He. A learning based branch and bound for maximum common subgraph problems. IJCAI, 2019.
Ciaran McCreesh, Samba Ndojh Ndiaye, Patrick Prosser, and Christine Solnon. Clique and constraint models for maximum common (connected) subgraph problems. In International Conference Principles and Practice of Constraint Programming, pp. 350-368. Springer, 2016.
Ciaran McCreesh, Patrick Prosser, and James Trimble. partitioning algorithm for maximum common subgraph problems. 2017.
10

---

Under review as a conference paper at ICLR 2021
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. NeurIPS Deep Learning Workshop 2013, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, (1(7540)):229-3 533, 2015.
Younghee Park, Douglas S Reeves, and Mark Stamp. Deriving common malware behavior through graph clustering. Computers & Security, 39:419-493 4300, 2013.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wasserstein averaging of kernel and distance matrices. In ICMI., pp. 2664-2672, 2016.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Staristical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Puttern Recognition (SSPR), pp. 287-297. Springer, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günneemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop (R2L 2018), NeurlPS 2018, 2018.
Anshumali Shrivastava and Ping Li. new space for comparing graphs. In Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 62-71. IEEE Press, 2014.
Zequn Sun, Wei Hu, and Chengkai Li. Cross-lingual entity alignment via joint atribuute-peserving embedding. In International Semantic Web Conference, pp. 628-644. Springer, 2017.
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 Modelling, Compu- tation and Optimization in Information Systems and Management Sciences, pp. 358-368. Springer, 2008.
Nikil Wale, Ian Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. ICCV, 2019.
Xiaoli Wang, Xiaofeng Ding, Anthony KH Tung, Shanshan Ying, and Hai Jin. An efficient graph indexing method. In ICDE, pp. 210-221. IEEE, 2012.
Duncan Watts and Steven Strogatz. Collective dynamics of 'small-world' networks. nature, 393 (6684):440, 1998.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserstein learning for graph partitioning and matching. In NeurIPS, pp. 3046-3056, 2019a.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov learning for graph matching and node embedding. 2019b.
Xifeng Yan, Philip S Yu, and Jiawei Han. Substructure similarity search in graph databases. In SIGMOD, pp. 766-777. ACM, 2005.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. SIGKDD, pp. 1365-1374. ACM, 2015.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with indepedendeeenneent embedding and hungarian attention. In ICLR, 2020. URL /ttpp::/ oppenreviww net www.:/erttooummtmee 2

---

Under review as a conference paper at ICLR 2021
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.
12

---

Under review as a conference paper at ICLR 2021
A DATASET DESCRIPTION
This section describes the datasets used for evaluating our model and baselines. Section B. describes the dataset we use for training GL.EEARCH as well baseline learning based graph matching models. We use the following real-world datasets for evaluation:
It is collection of small-sized chemical compounds (Wale et al. 2008) whose nodes labeled indicating atom type. We form 100 graph pairs from the dataset whose average graph size (number of nodes) is 28.73.
Nc1109:
ROAD: The graph is a road network of California whose nodes indicate intersections and end- points and edges represent the roads connecting the intersections and endpoints (Leskoved) et al., 2009). The graph contains 1965206 nodes, from which we randomly sample con- nected subgraph of around 0.05% nodes twice to generate two subgraphs for the graph pair G1 =V1, and G2 (V2, E2)-
DBEN, DBZII, and DBPD: It is dataset originally used in a work on cross-lingual entity alignment (Sun et al. 2017). The dataset contains pairs of DBpedia knowledge graphs in different languages. For DBEN, we use the English knowledge graph and sample 10% nodes twice to generate two graphs for our task. For DBZH, we sample around 10% nodes from the knowledge graph in Chinese. For DBPD, we sample once from the English graph to get G1 and sample once from the Chinese graph to get G2. Note that although the nodes have features, we do not use them because our task is more about graph structural matching rather than node semantic meanings, and leave the incorporation of continuous node initial representations future work.
ENRO: The graph is email communication network whose nodes represent email ad- dresses and (undirected) edges represent at least one email sent between the addresses (Klimt & Yang 2004). From the total 36692 nodes, we sample around 10% nodes generate the graph pair.
COPR: An Amazon computer product network whose nodes represent goods and edges represent goods frequently purchased together (Shchur al. 2018). The graph contains 703655 nodes from which we sample around 0.5% to get the pair we use.
CIRC: This is a graph pair where each graph is a circuit diagram whose nodes represent devices/wires and edges represent the connecting relations between devices and wires. In other words, each node is either device or a wire, and the entire graph is bipartite. The two graphs given are known to be isomorphic and do not perform any sampling. Nodes have labels about the type of the device/wire. In real world, the successful matching of circuit layout diagrams an essential process in circuit design verification.
interaction network whose nodes represent proteins and edges represent physical interaction between proteins in human cell (Agrawal et al.) 2018). From the 21557 nodes, we sample around 10% nodes to generate the pair used in experiments.
HPPI: is human
The details of all the graph pairs can be found in Table 4
Table 4: Details of real-world graph pairs used in evaluating the performance of baseline methods and GLSEARCH.
Name
Deseription
122
[1
[1
V4
V4
ROAD
Road Network
1114
652
1454
822
1.305
1.261
DBEN
Knowledge Graph
1945
1945
6242
5851
3.209
3.008
DBZH
Knowledge Graph
1907
1907
4856
4948
2.546
2.595
DEPD
Knowledge Graph
1945
1907
6242
4856
3.209
2.546
ENRO
Email Communication Network
3369
3369
46399
50637
13.772
15.030
CoPR
Product Co- fo-purchasing Network
3518
3518
56028
40633
15.926
11.550
CIRC
Circuit Layout Diagram
4275
4275
6128
6128
1.433
1.433
HPPI
Protein-
Protein Protein-Protein
Interaction Network
2152
2152
54910
54132
25.516
25.154
13

---

Under review as a conference paper at ICLR 2021
For synthetic datasets, we generate graph pairs using the Carabási-Albert (BA) (Barabási & Albert 1999) algorithm (edge density set to 5), the Lenos-Rééni (ER) (Gilbert 1959) algorithm (edge density
set to 0,08), and the Watts Stroggtzz (WS) (Watts & Strogatz set to 0.2 and ring density set to 4), respectively.
1998) algorithm (rewiring probability
B DETAILS ON DQN AND TRAINING GLSEARCH
B. TRAINING DATA PREPARATION: CURRICULUM LEARNING
Curriculum learning (Bengio et al. 2009) is a strategy for training machine learning models whose core idea is to train a model first using "easy" examples before moving on to using "hard" ones. Our goal is to train general model for MCS detection task which works well general testing graph pairs from different domains. Therefore, we employ the idea of curriculum learning in training our GLSEARCH. More specifically, we prepare the training graph pairs in the following way:
The first curriculum consists of the easiest graph pairs that small: (1) We sample 30 graph pairs from AIDS (Zeng et al.] 2009), a chemical compound dataset usually for graph similarity computation (Bai
Curriculum 1:
2019) where each graph has less than or equal to 10 nodes; (2) We sample 30 graph pairs from LINUX (Wang et al. 2012), another dataset commonly used for graph matching consisting of small program dependency graphs generated from Linux kernel; (3) So far we have 60 real-world graph pairs. We then generate 60 graph pairs using popular graph generation algorithms. Specifeally, we generate 20 graph pairs using the BA algorithm, 20 graph pairs using the ER algorithm, and 20 graph pairs using the Stroo-Sttogatz WS algorithm, respectively. Details of the graphs can be found in T In summary, the first curriculum contains 120 graph pairs in total.
Curriculum 2: After the first curriculum, each next curriculum contains graphs that larger and harder to match than the previous curriculum. For the second curriculum, we sample 30 graph pairs from PrC (Shrivastava & Li 20044) collection of chemical compounds, 30 graph paris from IMDB (Yanardag & Vishwanathan 2013). a collection of ego-networks of movie actors/actresses. and generate 20 graph pairs again using the BA, ER, and WS algorithms but with larger graph sizes.
Curriculum 3: For the third curriculum, we sample 30 graph pairs from MUTAG (Debnath ct al.] 1991), a collection of chemical compounds, 30 graph paris from REDDIT (Yanardag & Vishwanathan, 2015), collection of ego-networks corresponding online discussion threads, and generate 20 even larger graph pairs using the BA, ER, and WS algorithms.
Curriculum 4: For the last curriculum, we sample 30 graph pairs from WEB (Riesen & Bunke 2008). a collection of text document graphs, 30 graph paris from MCSPLAIN- CONNECTER TED (McCreesh et al., 2017). a collection of synthetic graph pairs adopted by MCSP, and generate graph pairs again using BA, ER, and WS algorithms but with larger graph sizes.
For each curriculum, we train the model for 2500 iterations before moving on to the next, resulting in 10000 training iterations in total.
B.2 TRAINING TECHNIQUES AND DETAILS
B.2.1
STAGE 1: PRE-TRAINING
For the first 1250 iterations, pre-train DQN with the supervised true target ye obtained as follows:
For each graph pair, we run the complete search, i.c. we do not perform any pruning for unpromising states. The entire search space is explored, and the future reward for every action can be found by finding the longest path starting from the action to a terminal state. small in the initial stage, such complete search can be affordable. Using Figure in the main text as an example, for the action that causes state to transition to state 6, the longest path is 0, 6, 7, 11, 12, 13 (or 0, 6, 11, 12, 14).
Since graphs
14

---

Under review as a conference paper at ICLR 2021
Table 5: Training graph details. For synthetic graphs. "ed", "p", and "rd" represent edge density, rewiring probability, and ring density, respectively.
Curriculum
Data Source
# Graph Pairs
AIDS
30
LINUX
30
Curriculum 1
BAm==16.d==5
20
FR:n=14,ed=0.14
20
WS
20
PTC
30
IMDB
30
Curriculum 2
BA:n=32.ed=4
20
ER:n=30,ed=0.12
20
WS:n=34..=00.211-2
20
MUTAG
30
REDDIT
30
Curriculum 3
BAm==48.ed=4
20
ERd==66.dd00.1
20
WSmm=50.p=0.2.dd44
20
WEB
30
MCSPLAIN-CONNEECTED
30
Curriculum 4
BAm==62,ed=3 ER:
20
20
WS:n=66.p=0.2.rd-2
20
Given the longest path found for each action, then compute y/ +1..-+?"+...+ where is the discount factor set to 1.0, L is the length of the longest path. In the example above, V/2 5, intuitively meaning that at state for the action that leads to state in future the best solution will have 5 more nodes. In contrast, the action 0 to has = 4. meaning the action 0 to 6 more preferred.
Given the true target computed for each action, the mse loss (y/= Q(t,, az))², where the batch size (number of sampled actions) set to 32.
the mini-batch gradient descents
B.2.2 STAGE 2: IMITATION LEARNING AND STAGE 3
For stage 2 (2500 iterations) and stage 3 (6250 iterations), train the DQN using the framework proposed in Mnih et al.) (2013). The difference is that in stage 2, instead of allowing the model to use its own predicted Q(s,, at) each state, let the model make decision using the heuristics by the MCSP algorithm, which serves as an expert providing trajectories in stage 2. We aim to outperform MCSP eventually after training using our own predicted Q(5e, (e) in stage 3.
Here we describe the procedure of the training process. In each training iteration, we sample graph pair from the current curriculum for which we run the DQN multiple times until terminal state is reached to collect all the transitions, i.c. 4-tuples in the form of (5t, Qe, St+1) where r; is I and Vi y max,' (( a'), and store them into global experience replay buffer, a queue that maintains the most recent L 4-tuples. In our calculations, L = 1024. Afterwards, at the end of the iteration, the agent gets updated by performing the mini-batch gradient descents over the mse loss (y, - Q(x, 22 where the batch size (number of sampled transitions from the replay buffer) is set to 32.
To stabilize training, adopt target network which is copy of the DQN network and use it for computing max, 7Q(s+41, a'). This target network is synchronized with the DQN periodically, in every 100 iterations.
Since at the beginning of stage 3, the q approximation may still be unsatisfactory, and random behavior may be better, adopt the epsilon-greedy method by switching between random policy and Q policy using a probability hyperparameter e. Thus, the decision is made as arg max where the our predicted Q(se, ax) for all possible actions (i.j) with probability; With probability,
15

---

Under review as a conference paper at ICLR 2021
the decision is random. This probability is tuned to decay slowly the agent learns to play the game, eventually stabilizing at a fixed probability. We set the starting epsilon to 0.1 decaying to 0.01.
B.3 DQN PARAMETER DETAILS
In experiments, we use SUM followed by an MLP for READOUT and DICON+MMXPPOO followed by an MLP for ICTERACT. Specifically, the MLP has 2 layers down-projecting the node embeddings from 64 to 32 dimensions. Notice that different types of embeddings require different MLPs, c.g. the MLP used for aggregating and generating graph-level embeddings is different from the MLP used for aggregating and generating subgraph-level embeddings.
For IDCONV+MAXPOOL. we apply a 1-dimensional convolutional neural network to each one of two embeddings being interacted, followed by performing max pooling across each dimension in the two embeddings before feeding into MLP generate the final interacted embedding. Specifically, the IDCONV contains a filter of size 3 and stride being 1. The MLP afterwards is again 2-layer MLP projecting the dimension to 32. As shown the main text, such learnable interaction operator brings performance gain compared to simple summation based interaction.
The final MLP takes four components, hgg INTERACT (hg., ht2),, h, = INTERACT (f+1 h.2). heDe. and po, each with dimension 32. It consists of 7 layers down-proj projecctrog the 22-dimensiional input (32 x 4) to scalar as the predicted q score. For every MLP used in experiments, all the layers except the last use the (LU(z) activation function. An exception is the final MLP, whose last layer uses the (LU(x) + as the activation function to ensure positive y output.
A subtle point to notice is the necessity of using either nonlinear readout or nonlinear interaction for generating the bidomain representation. Otherwise, if both operators are a simple summation, the representation for all the connected bidomains (bpe) is essentially the global summation of all nodes in all the connected bidomains. In other words, the nonlinearity of MLP in the readout operation or the interaction operator allows model to capture the bidomain partitioning information in hyee
C NOTES ON SEARCH
C.I COMPARISON WITH MCSP AND McSP+RL
The key idea of our model is that under a limited search budget, by exploring the most promising node pairs first, search can reach a larger common subgraph solution faster. In other words, for small graph pairs, all baseline models would obtain the exact MCS result as long the search algorithm runs to complete, i.c. the stack is eventually empty, mcaning no more actions to select and no more states to backtrack to (all states have been visited and fully expanded to all possible next states).
However, for large graph pairs, the task is NP-hard, and the complete search becomes nearly impossible. Exceptions exist though: For example, if the pruning condition based the upper bound estimation is powerful enough to prune many states, i.e. lines 12-14 in Algorithm in the main text, the search may finish in relatively few iterations. However, we observe that the state-of-the-art solvers, MCSP and McSP+RL, cannot finish completely for all the graph pairs used in testing. Instead of trying improve the upper bound estimation to be more exact, in this paper, our goal is learn better node pair selection policy, i.c. line 17 in Algorithm 1, to replace the heuristics used by baseline solvers.
Notice that our focus on node pair selection policy instead of upper bound estimation implies that better selection policy would mean the search can quickly find a larger solution and update its best solution found so far mar.Sol. This not only mean when the search budget is used up, the result returned is larger, but also mean that for subsequent iterations (before the iteration limit is reached), more states would be pruned by checking UB, < |maz:Sol], thus further helping the search. In summary, in our framework, the upper bound computation strategy remains unchanged, yet the successful node pair selection policy benefits the search in two major ways.
Since we use MCSP in the imitation learning stage of training our DQN, and compare with MCSP and McSP+RL in the main text, describe their node pair selection heuristics. For MCSP, when entering new state, it first selects the node with the largest node degree in G, and then enumerates through all the nodes in Go in descending order of node degrees. In the original implementation
16

---

Under review as a conference paper at ICLR 2021
provided by McSP, this is achieved by recursive function calls. After all the nodes in G2 are visited, Le. the depth-first search of all the node pairs (i.j) finishes where i is the largest-degree node in I1 and is every node in G2. the algorithm seleets the second largest-degree node in 91, and repeats the enumeration of nodes in G2. After all node pairs are exhausted, the function returns and the algorithm essentially backtracks to the parent state. If the current state is the root node in the search tree, the search is complete and the exact MCS is returned. However, as noted earlier, for large graph pairs it is almost impractical to search exhaustively and budget on the amount of search conducted has to be applied. Thus, which node pairs to visit first matters lot for successfully extracting large solution for large input graphs. However, as seen in Figure [0 and contain large-degree nodes, since large-degree nodes tend to form more complicated subgraphs which are harder to match in the other input graph compared to simpler subgraphs like chain. Thus, by visiting large-degree nodes first, MCSP may not always yield a large solution fast.
many cases the true MCS does not
In contrast, McSP+RL maintains a promising score for each node and iteratively updates the scores as search visits more states. The update formula is based on the reduction of upper bound for search, where upper bound in an overestimation of future subgraph size. As search makes progress, the scores updated in each iteration, and nodes which cause large reduction in upper bound computation get large reward. This has the limitation that for each new graph pair, the scores associated with each node must be re-initialized to 0 and re-learned, since there is neural network and the only learnable parameters are the scores for each node. At the beginning of search, all scores are initialized to O, and the search has to break the tie using another heuristic. while once trained, our GLSEARCH can be applied to any new testing pair, and at the beginning of search, the learned parameters in GLSEARCH starts benefit the search. In other words, the whole design of McSP+RL can be regarded as search framework with shallow learning (without neural networks or training via back-propagation, GLSEARCH is the first model to use deep learning for node pair selection.
Another limitation of McSP+RL is that the scores maintained for nodes reflect the potential ability of a node to reduce the upper bound for future iterations in the current search, which is indirect as the MCS aims to find the largest common subgraph, not the reduction of upper bound. Moreover, the upper bound itself is an overestimation of future subgraph size, which may or may not be close enough to the actual best future subgraph size. In contrast, aim to predict the score for actions which directly reflect the best future subgraph size. Overall, the lack of deep learning ability causes McSP+RL not only re-estimate the scores for the nodes for each new graph pair, but also to resort to the upper bound heuristic for updating the scores.
To ensure the budget on search iterations is applied consistently for all the models evaluated in the main text, we adapt the original recursive implementation of MCSP in C++ to an iterative implementation in Python so that all the models compare with each other in the same programming language and the same search backbone algorithm. To be specific, we check the iteration count at the beginning of every search iteration and early stop the search if the pre-defined budget is reached.
C.2 TREE VS SEQUENCE
At this point, having illustrated the differences between GLSEARCH and McSP and MCSP+RL, it is worth clarifying whether GLSEARCH search yields tree or sequence in different stages. For training stage and 2, as described in Section B.2] our model is just randomly initialized and not well trained, so the pre-training and imitation learning stages use the policy of MCSP instead of using its own predicted q scores. In stage 1, the complete search is performed to provide maximum amount of supervised signals, i.c. ye- but in stage 2. we start using the RL training framework, i.c. experience replay buffer, target network, etc. so we run the agent multiple times until terminal state is reached, corresponding to a sequence in tree, which starts from the root node and ends at leaf node. For stages 2 and 3, since sequences are generated instead of trees, for each sequence, the upper bound check always passes, because the pruning only happens when backtracking is allowed, i.e. a tree is formed. To see this more clearly, recall the pruning only happens if UB, < maazool] in Algorithm I in the main text. However, during the sequence generation process, max keeps increasing by one each time new state is reached. Since UB, + Scur overestimate((s, (s:). UB, > [curSSll| for non-terminal s,, and [curSol] = maazSol], and thus UB, > |maxSol), and thus the pruning never happens.
17

---

Under review as a conference paper at ICLR 2021
At the beginning of stage 2, the sequences we collect usually not long, since the policy is the same as MCSP in stage 2. However, in stage 3, we start using our predicted Q(st, az) to get such sequences, and at the end of training, when we apply GLSEARCH to testing pairs during inference, as shown in the main text, we perform better than MCSP and all the other baselines. In inference, we completely rely our predicted scores as the policy, and search tree is yielded, although the tree is not complete since the graph pairs are large and search budget is reached.
C.3 TERMINAL CONDITIONS
This section discusses on how terminal state, i.e. a leaf node in the search tree, is determined. Notice our definition of bidomain (equivalence class) does not include node labels, and in each iteration, we allow the matching between nodes in the same bidomain with the same node label. We consider the node labels as additional pruning each bidomain, i.e. we further only allow nodes with the same label to match within bidomain when considering actions to be fed into DQN. Suppose 91 and G2 are connected graphs. There are two cases:
Case I: Nodes are unlabeled (or equivalently, all the nodes have the same label). The terminal condition is that there is no non-empty connected (adjacent) bidomains. For example, there are still some adjacent bidomains, but for each bidomain (V21, 2222, at least one of 1 and V/22 is empty (containing no nodes), so there is no nodes to match in each bidomain. Examples are states 3 and 6 in Figure 6
Case 2: Nodes are labeled. For the terminal condition, there may be still some non- non-empty connected bidomains, but the node labels do not match causing more node pairs to select from. For example, one bidomain contains k1 with C and N as node labels and V/22 with H node label. Then essentially there is more node pairs left.
C.4 PROMISE-BASED SEARCH: IMPROVING SEARCH WITH BACKTRACKING
r(0,6) + (m(6.77
yf ((7.Q(7.aa)
ooo
Figure 5: An illustration of how the estimated cumulative sum of rewards is computed for state The expected maximum cumulative sum of rewards obtainable from state 7 is equivalent to the sum of rewards up state 7 (r(0, 6) + (r,6, 7)) and maximum Q-score at state ()² max; Q(7, aq)). For MCS detection, r(st. 1 = since one new node pair is selected.
Because it computes Q-values, GLSEARCH can leverage more information than baselines when exploring the search space. Specifically, Q-values may be used to compute predicted maximum cumulative sum of rewards for every search state, 8t, in the search tree: Σ/= (r((s,, 85+1)
yd max; ((s where .)--)) can be the Q-score predicted by GLSEARCH. This score intuitively encodes maximum subgraph size achievable from every search state, and, for brevity, we will refer call it the promise score. An example of how to compute this score is shown Figure 5 Because promise scores are comparable across all search states, GLSEARCH can consider the best possible state to visit from any search state, whereas baselines can only consider the best possible state to visit from the current search state. GLSEARCH can also backtrack to more promising search states at any iteration of the search process, whereas past MCS models backtrack only when all future search states from the current state are exhausted.
Unlike MCSP or McSP+RL, GLSEARCH is optimized to find the largest common subgraph in one try, not to prune the search space. This is because, in practice, even with advanced pruning
18

---

Under review as a conference paper at ICLR 2021
techniques, it is not practical to exhaust the entire search space for large graphs. As consequence, GLSEARCH may fall into local solutions if it strictly follows the McSP search algorithm (Algorithm 1 of main text). Thus, GLSEARCH improves upon McSP search by backtracking an earlier state with the highest predicted maximum cumulative sum of rewards when the current best solution not improved upon within fixed number of iterations. In practice, set this number 3.
In implementation, whenever a new state, S141 is reached from state 8, by taking action a", promise scores for both 1 and 8, are computed tell the search algorithm where backtrack. We associate the promise value Σj= "'r(s. $J+1) + ((( a²) to St+1 and update the promise value of s with Σ 20=0 ?"(s,, + 7 max (++t; a), because a" is excluded in future iterations of search from state s (line 18 of Algorithm of main text). In addition pushing states to the stack on line 19 and 21 of Algorithm in the main text, we also push states to an additional priority queue. Thus, whenever the backtrack condition is satisfied, cumulative sum of rewards by popping the priority queue instead of the stack.
retrieve states with the highest expected
C.5 NOTES ON EQUIVALENT STATES AND MULTIPLE GROUND TRUTHS
10
100
State 2
State
S1
G2
10
State 0
State
State
Figure 6: An example illustrating the idea of equivalent states. It is important note that states
3, 5, 6 are different since their node-node mappings are different. However, the solutions derived from both states and have the same subgraph size, In other words, there can be multiple ways to arrive at the same solution size, with different underlying sequential processes to reach the final states.
It is well known that for the MCS detection task, there can be multiple ground truth solutions with the same subgraph size. For example, in Figure both states 3 and correspond to the same subgraph size but the states 3 and 6 are different due their different node-node mappings. Our model maintains the node-node mappings for each state, and therefore states and would be reached as different states. It is important note that for large graph pairs, reaching both states 3 and 6 usually does not happen, since the search would first reach state and need many iterations to backtrack to state 0 and further many iterations reach state 6.
There is an even more subtle point in Figure 6 Suppose the search first matches node a to node denoted as state then matches node b node 2, leading state After several iterations, backtracks to state 0 and chooses to match node b to node 2, denoted as state then matches node a node 1, denoted as state y. Although states and x are different, but states and y are equivalent, since both states 2 and have the same node-node mapping, i.e. a to 1 and b to 2. Thus, the search maintains an additional set of visited states and at each time new state is reached, a checking performed to avoid revisiting the same state twice.
The node-node mapping is is an important component of the definition of state, not only because differentiates the otherwise equivalent states, but also because different node-node mappings can lead to different final states and future reward (and thus must be considered by the design of DQN). Suppose the bidomain "01" in state 1 contains more than two nodes, i.e. there many nodes connected to b in G besides node d and many nodes connected to node in G2 besides node 3. Then state 2 is intuitively more preferred state compared to state 5, since the matching of node to node
19

---

Under review as a conference paper at ICLR 2021
2 allows more node pairs to be matched to each other in future, thus larger action space in state 2. The value associated with state 2 thus should be larger than state
C.6 DEALING WITH LARGE ACTION SPACE
For large graph pairs, the successful detection of MCS not only depend on the design of our critical DQN component as well as its training. but also rely on techniques which prune the large action space at each state.
The bidomain partitioning idea has been outlined in the main text which effectively reduces the action space size by only matching nodes in the same bidomain. However, for extremely large and dense graphs, the bidomains may not split the rest of the graphs enough and the action space may still be too large. For example, consider two fully connected graphs 91 and Go i.e. for every two nodes there is an edge. Then initially, there is nodes selected, and there is only one bidomain consisting of all the node pairs. What is worse, at any state, there is always only one bidomain consisting of all the node pairs in the remaining subgraphs. Therefore, reduce the action space further, we only compute the y scores for N₂ nodes at most in each state. Specifically, we first sort the candidate bidomains by their size in ascending order, and select the first N₂ small bidomains. Next, we sort the nodes in each bidomain by degree in descending order and select the first Na/N,, nodes with large node degrees. For our experiments, N₁, = 1 and N₂ 20. We find, in practice, these settings do not drastically alter performance. Denote C N2. which is a constant representing the most amount of node pairs the DQN looks at per iteration. Then, in each iteration, the time complexity of GLSEARCI is (CIi). Suppose on average, each one of the C1 node pairs requires C2 amount of computations. In practice, for a simple implementation, all the C1 node pairs can be computed sequentially, resulting in C₁C₂ running time. However, various techniques can be applied in practice, c.g. batching the C1 computations, which will further reduce the bounded running time. In implementation, we apply some optimizations to decrease the running time, c.g. computing the node embeddings at the beginning of search and caching them for the entire search during inference. However, we believe further optimization of implementation is possible and leave for future efforts. In experiments, we set the search budget to 7500 iterations for all baselines to compare and find which method can quickly find larger solution in terms of iterations.
In future, additional techniques for pruning the action space and speeding up the computation can be explored. For example, instead of bounding the computation be Na. we may perform a hierarchical graph matching by first running a clustering algorithm and then matching clusters which will be bounded by the number of clusters. Another possible direction is to learn an additional Q function learning which node is more promising instead of which node pair, i.e. Q( 0g (6) for node and QSe,, ( for node; j in the action de- = (i,j). We suppose such additional Q function may bring further performance gain.
C.7 ANALYSIS OF TIME COMPLEXITY
Overall the branch-and-boume search has exponential worst-case time complexity due to the NP-hard nature of exact MCS detection, and our goal is to use additional overhead per search iteration to make "smarter" decision each iteration so that we can find a larger common subgraph faster (in less iterations AND real running time). Per iteration, our model requires the neural network operations to compute a Q score instead of simply using a degree heuristic which is O(1). Here we analyze the time complexity of these neural operations:
To compute the node embeddings, the complexity is the same as the GNN model, which in our case is O(D + (&]) for GAT (since nodes must aggregate embeddings from neighbors and attention scores must be computed for each edge). Notice the node embeddings are computed by local neighborhood aggregation, and will not be updated in search, and therefore compute the node embeddings only once at the beginning of search, and can be cached for efficiency.
At each iteration, to compute a Q score for a state-action pair, we run Equation 3 which requires computing the whole-graph graph, subgraph, and bidomain embeddings. Overall the time complexity is O(V] [V,l) where V, is the number of nodes in the currently matched subgraph. The whole-graphe embeddings do not change across search, so they only need to be
20

---

Under review as a conference paper at ICLR 2021
computed once at the beginning. The subgraph embeddings can be maintained incrementally, i.c. adding new node embeddings as search grows the subgraph. The bidomain embeddings are computed via series of READOUT and INTERACT operations (Equation 2 For READOUT: We use summation followed by MLP so the runtime is O(V] V.]): For INTERACT: We use a 1D CNN followed by MLP which depends the embedding dimension set to a constant, and does not depend on the number of nodes in the input graphs.
D BASELINE DESCRIPTION AND COMPARISON
For all the models used in experiments, we evaluate their performance under the same search framework, i.e. with consistent search iteration counting. upper bound estimation, etc. MCSP and McSP+RL use heuristics to select node pairs, which is ineffective as shown in the main text and has been described in Section C.1 Therefore, this Section focuses on the comparison with the rest baselines, i.e. GW-QAP (Xu et al. 2019a). I-PCA (Wang et al. 2019), and NEURALMCSS (Bai et al. 2020b)
GW-QAP is a State-of-theeart graph matching model for general graph matching. The task is not about MCS specifically, but instead about matching two graphs with own criterion based on the Ktromv--Wassersee
discrepancy (Peyré et al., 2016). Therefore, we suppose the matching matrix Y generated for each graph pair can be used as a guidance for which node pairs should be visited first. In other words, we pre-compute the matching scores for all the node pairs before the search starts, and in iteration, we look up the matching matrix and treat the score as the q score for action selection. I-PCA and NEURALMCS essentially compute matching matrix too, and it is worth mentioning that all the three methods cannot learn a score based on both the state and the action. They can be regarded as generating the matching scores based on the whole graphs only without being conditioned and dynamically updated on states and actions.
I-PCA is state-of-the-arr image matching model, where each image is turned into graph with techniques such as Delaunay triangulation (Lee & Schachter 1980). It utilizes similarity scores and normalization perform graph matching. We adapt the model our task by replacing these layers with 3 GAT layers, consistent with GLSEARCHL As the loss is designed for matching image-derived graphs. we alter their loss functions to binary cross entropy loss similar to NEURALMcS which will be detailed below.
NEURALMcS is proposed for MCS detection with similar idea from I-PCA that matching matrix is generated for each graph pair using GNNs. However, they both require the supervised training signals, i.e. the complete search for training graph pairs must be done to guide the update of I-PCA and NEUR ALMCS. In contrast, GLSEARCH is trained under the RL framework which does not require the complete search (in stage 2 and 3, only sequences are generated as detailed Section C.22). This has the benefit of exploring the large action space in a "smarter" way and eventually allows our model to outperform I-PCA and NEURALMCSS In implementation, the complete search is not possible for large training graph pairs, instead apply a search budget and use the best solution found so far to guide the training of I-PCA and NEUR MCC.
Regarding the subgraph extraction strategy, for all the baselines, algorithm, which is the sfate-of-the-art search designed for MCS (McCreesh et al., 2017). However, as mentioned in Section [ection[C.4] only our model is equipped with the ability to backtrack in a principled way. The main text shows the performance gain to GLSEARCH brought by the backtracking ability.
the same branch and bound
E
MORE RESULTS WITH ANALYSIS
E.1 BEST SOLUTION SIZES ACROSS TIME
Figure 7 shows that under the budget we set, for the large real-world graph pairs, all the methods reach a "steady state" where the best solution found so far no longer grows. This means the search continues but the search cannot find a larger solution, illustrating the fact that search gets "stuck". In theory, given infinitely many iterations, all the models will eventually find the true MCS, which is the largest, but since the task is NP-hard, the search space can be exponential in the worst case (subject to pruning but in all the testing graph pairs the search has not finished yet), such budget has to be
21

---

Under review as a conference paper at ICLR 2021
applied to search. At the end of the 7500 iterations, though, all the models have made "mistakes" (visiting unpromising states) and in order to find even larger common subgraphs, the search needs to backtrack potentially many times to fix those "mistakes" (backtracking to very early state).
Admittedly, there is always the possibility that for more iterations, some baseline method may find larger solution. Besides, in each iteration GLSEARCH does take more running time overhead as shown in Table 6 However, the point of our model is to quickly find a larger solution in as few iterations possible, not to find large solution given too many iterations. In other words, the goal of GLSEARCH is to be smart enough to quickly find a large solution instead of purely finding a good solution. Figure 7 shows that GLSEARCH not only finds solutions larger than baselines when the 7500 iterations budget is reached but also finds larger solutions faster than baselines before the budget is reached.
Table 6: Average running time per iteration (msec).
Method
ROAD
DBEN
DEZH
DRPD
ENRO
COPR
CIRC
HPP1
MCSP
2.040
10.724
1.415
0.974
1.722
2.891
1.776
0,498
McSP+RL
0.894
6,834
2.103
1.247
2.166
3.107
2.080
0.559
GW-QAP
0.548
0.834
0.546
4.692
1.041
3.419
1.550
0.546
I-PCA
1.152
1.797
0.967
0.897
1.739
2.725
3.792
0.636
NEURALMCS
2.394
4.172
4.648
5.667
9.610
9.788
7.471
15.742
GLSEARCH-RAND
17.392
66.418
67.342
67.946
163.005
71.972
655.447
83,488
GLSEARCH
8.132
66,552
71.409
96.262
135.087
51.181
37.377
60.509
In addition to reaching a larger solution less iterations, GLSEARCH also reaches better solutions with respect to runtime, shown in Figure 8 Notice. GLSEARCH finds the same large subgraph in 10 minutes as in 7500 iterations. Although per iteration, it is slower than MCSP per iteration, GLSEARCH finds larger solution in usually less than a minute. Moreover, can be further optimized. Note, we adapted all baselines to run on Python for fair comparison, and made sure the search iteration counting is consistent across all baselines and the results shown in the main text. At this stage, our main goal is to explore the idea of "learning to search" which has been experimentally verified be a promising direction of research, and leave the efforts of implementation optimization using various techniques as future focus.
implementation
E.2 ADDITIONAL ABLATION STUDY
Table showw that pre-training and imitation learning benefit the performance under four out of the eight datasets. On ENRO and HPPI, without pre-training, our model performs better, which may be attributed to the fact that they are dense graphs (Table 4 while the training graphs used in stage I are relatively small and sparse (Section B.I
Table 7: Contribution of pre-training and imitation learning to the performance of GLSEARCH. "no-sup" denotes the removal of the pre-training stage (The first 3750 iterations: IL; The last 6250 iterations:
Normal QDN training); "no II." denotes the removal of the imitation learning stage (The first 3750 iterations: pre-training: The last 6250 iterations: normal DQN training); "no sup; no II." indicates the entire training (10000 iterations) is normal DQN training.
Method
ROAD
DBEN
DBZH
DBPD
ENRO
COPR
CIRC
HPP1
GLSEARCH (no sup)
0.557
0.957
0.946
0.904
L.000
0.999
1.000
1.000
GLSEARCH (no IL)
1.000
0.933
0.965
0.887
0.357
0.875
0.666
0.632
GLSEARCH (no sup: no IL)
0.678
0.907
0.896
0.837
0.401
0.949
0.949
0.651
GLAEARCH
0.879
1.000
1.000
1.000
0.412
1.000
0.855
0.688
BEST SOLUTION SIZE
149
486
465
471
1318
790
4112
587
Table 8 shows that the promised-based search improves the performance under four out of the eight datasets. For the other four datasets, the performance does not change, indicating that the backtracking to earlier promising state based the DQN output least does not hurt the performance. In the cases like ENRO and HPPI, whose average node degrees are large, the promise- rromise-based search improves the performance by large amount, showing the usefulness of the proposed strategy.
22

---

Under review as a conference paper at ICLR 2021
220
226
80
200
100
BeSp
2500 ior coraations
Scarch ricaatinss
(a) ROAD
(b) DBEN
300
100
Stee Solutren Found
.00
200
M.5p
PcSp-Rt
OLSearch land
9c5p-Rt
CLSearch- Rand
OLsearch
5M ooe ousearch
2000
2000
3000
4300
5000
6003
3330
1000
3000
8.00
5000
8000
3000
(c) DBZH
(d) DBPD
300
700
300
400
Bext
500
200
200
Search land
GeGearch
DN-24>
CLSsarch
DN-OK
CLSearch
IPCA
2000
2000
3000
4303
5000
6092
3330
2000
2006
3000
4000
5000
6000
1000
Eienatione
(e) ENRO
(f) CoPR
2000
400
3000
200
2000
200
1593
Xc2p
X030
MPKS
Mc
CLGmach-laad
Soarch Iteratins
Search Eneations
(g) CIRC
(h) HPPI
Figure 7: For each method, we maintain the best solution found so far in each iteration during the search process. We plot the size of the largest extracted common subgraphs found so far vs search iteration count for all the methods across all the datasets. The larger the subgraph size, the better ("smarter") the model in terms of quickly finding a large MCS solution under limited budget for large graphs.
23

---

Under review as a conference paper at ICLR 2021
26
80
200
100
BeSp
Buntamm
Buntamm
(a) ROAD
(b) DBEN
300
800
Found
Found
.00
200
9cSp-Rt
9150
OLSearch- lard
Stee
9c5p-Rt
GLSearch-i Rand aiseanc
0Lsearch
(c) DBZH
(d) DBPD
300
700
200
Bert
500
200
200
Search
GiGearch
D2-2A>
CLSsarch
DN-OK
CLSwarch
PEA
IPCA
250
300
400
50c
600
325
259
300
400
Sce
600
Runt Rurdime (sec)
Runtiine (se:)
(e) ENRO
(f) COPR
P:Sp
400
3500
200
300
200
MPKS
CLSmach-land
Buntiime
Runttine
(g) CIRC
(h) HPPI
Figure 8: For each method, we maintain the best solution found so far in each iteration during the search process. We plot the size of the largest extracted common subgraphs found so vs the real running time for all the methods across all the datasets. The larger the subgraph size, the better ("smarter") the model in terms of quickly finding a large MCS solution under limited budget for large graphs.
24

---

Under review as a conference paper at ICLR 2021
Table 8: Contribution of promise-based search (Section C.4 to the performance of GLSEARCH. "no promise" denotes that the search does not use the proposed promise- based search, i.e. it does not backtrack to an earlier state the search makes no progress after a certain amount of iterations, and instead, it continues the regular branch and bound search.
Method
ROAD
DBEN
DBZH
DBPD
ENRO
COPR
CIRC
HPPI
GLSEARCH (no promise)
0.879
1.000
1.000
1.000
0,412
1.000
0.855
0.688
GLSEARCH
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
BEST SOLUTION SIZE
131
508
482
521
543
791
3515
404
E.3
SCALABILITY STUDY
GLSEARCH can scale to very large graphs containing tens of thousands of nodes. To verify this, we generate 6 large synthetic graphs (3 graph pairs) using the BA, ER, and WS algorithms, each with 10000 nodes, and ran GLSEARCH against heuristic-based baselines for 7500 iterations. Our model is superior in all instances, as shown in Table g
Table 9: Results of GLSEARCH to even larger networks. Each synthetic dataset consists of one graph pair labeled as (generation (ggorithm)-(nmmbll of nodes each graph). For BA graphs, we set the edge density to 4. For ER graphs, set the edge density to 0.0016. For WS graphs, we set the rewiring probability to 0.2 and ring density to 4.
Method
BA-10k
ER-10k
WS-10k
McSP
0.952
0.975
0.911
McSP+RL
0.964
0.975
0.911
GLSEARCH
1.000
1.000
1.000
BEST SOLUTION SIZE
3172
2190
4839
E.4 RESULTS ON GRAPH PATRS WITH KNOWN MCS SIZE LOWER BOUND
To better understand the quality of subgraphs found by GLSEARCH, we construct new datasets with known lower bound MCS sizes. This is accomplished through generating 2 new graphs that share common subgraph from the existing large real-worls graph datasets. For each real-world graph, Go. we randomly extract 3 different subgraphs of the same size, So. S1, and S2, by running breadth first search from different starting nodes and extracting the explored induced subgraph. To construct new graph pair, (G1, G2), we form G1 by connecting Sy to S₁ with 20 random edges and form G2 by connecting Sg to S2 with 20 random edges. Thus, connections between S, nodes are the same in both Gn and G2, but connections between G1 \. So and G2 So are different. Notice, the lower bound of MCS size these new datasets would be |So]. and we name the new dataset by adding 'ss' to the parent dataset's name.
Table 10: Results on graph pairs with a common core subgraph (lower bound of MCS), with fixed runtime of 10 minutes.
ROAD-SS
DBEN-SS
DBZH-SS
ENRO-SS
COPR-ss
HPPI-SS
Method
444
778
762
1346
1406
860
MCSP
0.588
0.466
0.544
0.216
1.000
0.233
McSP+RL
0.588
0.466
0.544
0.214
1.000
0.233
GLSEARCH
1.000
1.000
1.000
1.000
1.000
1.000
BEST SOLUTION SIZE
388
349
672
CORB (Lower BOUND) SIZE
222
389
381
673
703
430
F EXTENSIONS OF GLSEARCH
GLSEARCH can be extended for flurry of other MCS definitions, e.g. approximate MCS, MCS for weighted and directed graphs, etc. via a moderate amount of change to the search and learning components. In this section, briefly outline what could be done for these tasks.
For approximate MCS detection, the bidomain constraint must be relaxed. One method of relaxing this constraint is allow sets of nodes belonging to different but similar bidomains match each
25

---

useful for producing new Under review as a conference paper at ICLR 2021
other. For instance, nodes in 91 from the bidomain of bitstring "00110" could map with nodes in G2 from the bidomain of bitstring "00111", since they are only 1 hamming distance away. Such relaxations as this can be made stricter or looser based on the application. The difference would be the search framework, thus the learning part of GL.SEARCH can largely stay the same.
Regarding MCS for graphs with non-negative edge weights, assuming our task is maximize the sum of edge weights in the MCS, instead of defining r. = 1, we can alter the reward function to be the difference of the sum of edge weights before and after selecting a node pair T. =ess wce)
Eees, where St is the edges of currently selected subgraph, s(".) is the edges of the subgraph after adding node pair, (u, v). and w=()) is a function that takes and edge and returns its weight. As the cumulative sum of rewards at step T' is the sum of edge weights Exe(t....Tyy: = EeE S. w(e) and reinforcement learning aims maximize the cumulative sum of rewards, we can adapt GI.Search to optimize for MCS problems with weighted edges.
Regarding MCS for directed graphs, the bidomaín constraint may be altered such that every bit the bidomain string representations now has 3 states: "0" for disconnected, '1' for connected by in-edge, and '2' for connected by out-edge. By considering the inward/outward direction of bitstring, we can guarantee the isomorphism of directed graphs. In this case, the search framework would only differ in how bidomains are partitioned. The learning part of Gl.Search would stay the same for this application.
More generally, we believe that there are many more extensions to GLSeerch in addition to the ones listed, such as disconnected MCS, network alignment, subgraph extraction. Further exploration of these are to be done as future efforts.
G RESULT VISUALIZATION
We plot the testing graph pairs and the results of MCSP and GLSEARCH in this Section. For all the figures except Figure 22 the other for the remaining subgraphs that cannot be further matched within the search budget. When plotting, we use larger circle size for nodes with larger degrees.
use colors for nodes, one for the selected subgraphs by the model,
In general, GLSEARCI is a less interpretable but more powerful method compared to heuristic baselines. That said, GLSEARCH presents some insights that may be hand-crafted heuristics.
GLSEARCH identifies "smart" nodes which can lead larger common subgraphs faster. For example, in the road networks (RoAD), as in Figure and and 11 our learned policy selects nodes with smaller degrees which allow for easier matching. The common subgraphs in road networks are most likely long chains, where nodes tend to have low degrees. In contrast MCSP always chooses high-degree nodes first leading to smaller extracted subgraphs.
GLSEARCH identifies "smart" matching of nodes which can lead to larger common subgraphs faster. For example, in the circuit graph (CIRC), we find 3 high-degree nodes that, when correctly matched, greatly reduces the matching difficulty of remaining nodes (see Figure 22 and 23 Upon further analysis, MCSP incorrectly matches the 3 high degree nodes (matching high degree node to low degree node). This happens when matching high-degree node correctly would break the isomorphism constraint (due to the current selected subgraph being incorrectly matched). GLSEARCH conscientiously adds node pairs so that it will always be able to match the 3 high degree nodes correctly.
We believe aspects of GLSEARCH design lead to this phenomenon. First, GLSEARCH encodes neighborhood structures that are k-hop away. McSP only looks at a single node and not its relationship with k-hop neighbors. Second, GLSEARCH considers scores on the node-node pair granularity, thus it will only match nodes with similar local neighborhoods. MCSP only considers scores on the node granularity, potentially matching 2 nodes with dissimilar neighborhoods together.
From these insights, one can potentially design a heuristic to first detect highly valuable nodes and guide a policy which prioritizes the matching of these critical nodes, or create better heuristics that consider not only uses the features of single node but also the similarity between the 2 nodes being matched.
26

---

Under review as a conference paper at ICLR 2021
Figure 9: Visualization of sampled graph pairs with the MCS results by GLSEARCH on Nc1109. Each chemical compound node has its label indicated in the plot. Extracted subgraphs are highlighted in green.
27

---

Under review as a conference paper at ICLR 2021
Figure 10: Visualization of MCSP result on ROAD. Extracted subgraphs are highlighted in green.
Figure 11: Visualization of GLSEARCH result on ROAD, Extracted subgraphs are highlighted in green.
28

---

Under review as a conference paper at ICLR 2021
Figure 12: Visualization of MCSP result on DBEN, Extracted subgraphs are highlighted in blue.
Figure 13: Visualization of GLSEARCH result on DBEN, Extracted subgraphs are highlighted in blue.
29

---

Under review as a conference paper at ICLR 2021
Figure 14: Visualization of MCSP result on DBZH, Extracted subgraphs are highlighted in pink.
Figure 15: Visualization of GLSEARCH result DBZH. Extracted subgraphs are highlighted in pink.
30

---

Under review as a conference paper at ICLR 2021
Figure 16: Visualization of MCSP result on DBPD. Extracted subgraphs are highlighted in purple
Figure 17: Visualization of GLSEARCHI result on DBPD. Extracted subgraphs are highlighted in purple.
31

---

Under review as a conference paper at ICLR 2021
Figure 18: Visualization of MCSP result on ENRO Extracted subgraphs are highlighted in blue.
Figure 19: Visualization of GLSEARCH result on ENRO. Extracted subgraphs are highlighted in blue.
32

---

Under review as a conference paper at ICLR 2021
Figure 20: Visualization of MCSP result on COPR. Extracted subgraphs are highlighted in blue.
Figure 21: Visualization of GLSEARCH result on CoPR. Extracted subgraphs are highlighted in blue.
33

---

Under review as a conference paper at ICLR 2021
Figure 22: Visualization of the original graph pair of CIRC. Different colors denote different node labels. There are node labels total: M (71.67%), null (10.41%) PY (9.1%), NY (8.23%), N (0.37%), and P (0.21%)
34

---

Under review as a conference paper at ICLR 2021
Figure 23: Visualization of MCSP result on CIRC. Extracted subgraphs are highlighted in yellow.
Figure 24: Visualization of GLSEARCH result on CIRC. Extracted subgraphs are highlighted in yellow.
35

---

Under review as a conference paper at ICLR 2021
Figure 25: Visualization of MCSP result on HPP1. Extracted subgraphs are highlighted in cyan.
Figure 26: Visualization of GLSEARCH result on HPPI. Extracted subgraphs are highlighted in cyan.
36


Reviews:
[{"review_id": "SfO1khIjQys", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Given two input graphs G1,G2 the maximum common subgraph detection problem asks to find an induced subgraph of both G1 and G2, with as many vertices as possible. In the recent years, there have been papers that introduce different heuristics for guiding the search of this subgraph within branch & bound algorithms. The main contribution of this paper is a combination of graph neural network embeddings and RL to guide the search more efficiently.  The function used to guide the deep Q-network is given in Equation (3). The paper performs a set of experiments on synthetic and real world pairs of graphs, where it is shown that it performs well in practice. The supplementary material provides more details on the experiments. \n\n- While the exploration strategy is more sophisticated than previous works, it comes at a greater computational cost than prior work. The experimental section should explain the trade-offs. Some of the plots from the supplementary material should be included in the main text, but the overhead that one needs to pay due to running GNNs and RL should be clearly stated. \n- In figure 2, shouldn't the output graphs, be induced, MCS subgraphs of the input graphs? While the figure serves the purpose of illustrating the exploration idea, it is a bit confusing. The caption and/or the text should better clarify the description of figure 2. \n- Are there some interpretable heuristics that you can derive by studying the policy of your algorithm? \n- It would be interesting to observe the effect of planted isomorphic subgraphs within larger graphs, with different connectivity patterns. For instance suppose we plant a large isomorphic subgraph on S={1..k} for convenience in two graphs G1,G2, but the connection between S, V/S is totally different between G1,G2. How would this affect GNN embedding for instance? \n- Given that some times inputs are noisy, are you aware of works where the goal is to find approximate MCS subgraphs, i.e., a small number of edges differing between the two subgraphs? This would cause issues to the branch-and-bound policy, but nonetheless it is interesting to think whether your method can be adapted to this case within a different search framework? What about when graphs have (non-negative) weights on their edges, or they are directed? Have you performed experiments on the latter two settings?  \n- The authors motivate their problem with applications in drug discovery, chemoinformatics etc. Such an application is missing. Furthermore, for many real-world applications the input graphs have specific structure that enable the discovery of large common induced subgraphs even in polynomial time provably.  See for example \"A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics\" by Leander Schietgat, Jan Ramon & Maurice Bruynooghe. While this fact does not render the contributions of the author(s) useless, it does reduce their value in terms of application domains, that are not appropriately discussed in the paper.\n\nOverall I found the paper to be interesting, but there are some non-trivial issues that need to be better addressed. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "IrsjyoIypTt", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 motivation of this paper is clear and interesting, as it’s important to explore the maximum common subgraph in biochemical domain. In this paper, the authors conduct a lot of experiments to demonstrate the effectiveness of the proposed method. Despite of this, the presentation of this paper requires improvement because many important details are missing, which makes it hard to follow. The time-complexity analysis might also be crucial to demonstrate the superiority of the proposed method over other baselines in terms of searching time. \n\nStrengths:\n1.\tThe motivation of this paper is clear and interesting.\n2.\tThe authors conduct many experiments to demonstrate the effectiveness of the proposed method.\nWeakness:\n1.\tThe last paragraph in Section 2.2 (the notion of bidomain) is hard to follow. It’s not clear what is k, and how bidomain partitions the nodes to get V’_{k,1} and V’_{k,2}, which from two different graphs G_1 and G_2. Many details regarding the notations are missing when a new equation is introduced, e.g. r_t in Factoring Out Action subsection. These missing details make it hard to follow. \n2.\tIn Figure 1, what’s the difference between 01 and 10?\n3.\tIn equation 2, what operation does INTERACT stand for? \n4.\tThe authors mention the maximum common subgraph detection problem is NP-hard, so it’s important to provide the time complexity of the proposed algorithms. However, in this paper, the authors do not provide any time complexity analysis or report the running time of the proposed method. In addition, in this paper, the authors mention that MCSP and MCSP+RL adopt the heuristics node pair selection policy but the proposed method is “learn-to-search” algorithm. It might be interesting to see whether the proposed method greatly reduces the search time compared with state-of-the-art algorithms as the number of nodes increases.", "extra_scores": {}, "extra_text": {}}, {"review_id": "9BXM6zs1gV", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper deals with the problem of Maximum Common Subgraph (MCS) detection, following a learning-based approach. In particular, it introduces GLSEARCH, a model that leverages representations learned by GNNs in a reinforcement learning framework to allow for efficient search. The proposed model has been experimentally evaluated on both artificial and real-world graphs, and its performance has been compared against traditional and learning-based baselines.\n\nStrong points:\n\n--- The paper deals with an important problem, and the overall learning-based formulation and solution look very interesting.\n\n--- The paper is well-written and most concepts, especially the proposed approach, have been clearly presented. Besides, the supplementary material describes in detail most of the aspects of the paper.\n\n--- The ablation study is interesting and demonstrates that the chosen architecture of GLSEARCH has consistent behavior.\n\n\nWeak points:\n\n--- My main concern is related to various aspects of the experimental evaluation of the proposed model. First, most of the datasets used in the evaluation seem to be unlabeled. In the basic formulation of the model though, the input graphs are allowed to be labeled. To my view, this makes the overall task more challenging. How consistent are the results in the case of labeled graphs?\n\n--- Second, the size of the input graphs is also an important parameter. Definitely, most heuristic baselines might not be able to scale to graphs with more than a few thousands of nodes, but I would be expecting to consider some large-scale network containing a few tens of thousands of nodes for the evaluation of GLSEARCH.\n\n\nTypos:\n\n--- Page 4, first paragraph: *F*or MCS, …\n--- Caption of Table 3: *Ablation*\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper present a new learning-based approach` to solve the Maximum Common Subgraph problem. All the reviewers find the idea of using GCN and RL to guide the branch and bound interesting although, even after reading the rebuttal, there are some important concerns about the paper.

The main issue raised by many reviewers are on scalability of the methods and motivation of the problem. It would be nice to add a scalability experiments on large networks(>1M nodes) to show that the method could potentially scale. In fact, the original motivation based on drug discovery, chemoinformatics etc. application is a bit weak because in those area domain specific heuristic should work better.

Overall, the paper is interesting but it does not meet the high publication bar of ICLR.
Decision: Reject