Maximum Common Subgraph (MCS) is defined as the largest subgraph that is commonly present in both graphs of a graph pair. Exact MCS detection is NPhard, and its state-of-the-art exact solver based on heuristic search is slow in practice without any time complexity guarantee. Given the huge importance of this task yet the lack of fast solver, we propose an efficient MCS detection algorithm, NEURALMCS, consisting of a novel neural network model that learns the nodenode correspondence from the ground-truth MCS result, and a subgraph extraction procedure that uses the neural network output as guidance for final MCS prediction. The whole model guarantees polynomial time complexity with respect to the number of the nodes of the larger of the two input graphs. Experiments on four real graph datasets show that the proposed model is 31.78× faster than the exact solver while achieving near-perfect accuracy in MCS detection.
This paper proposes a novel algorithm NeuralMCS for maximum common subgraph (MCS) identification. The proposed algorithm consists of two components. One is a neural-network model based on Graph Matching Networks (GMN, Li et al, 2019) to learn a node-to-node matching matrix from examples of the ground-truth MCS results. Another is the algorithm called GSE (Guided Subgraph Extraction) to obtain an MCS by making an explicit assignment from the estimated matching matrix by the NN model. Experimental comparisons are made to other NN-based approaches combined with threshold-based assignments by the Hungarian algorithm (w.r.t the accuracy) and to a state-of-the-art exact algorithm MCSplit, and show the effectiveness of NeuralMCS.
This paper proposes an interesting method for MCS detection which would have large application interests. Though the basic idea is nice,  the reported performance gains would be a bit less convincing due to the following evaluation problem and its weak novelty. 
The algorithm has two parts, and the first NN part to learn a matching matrix is mostly based on the already existing algorithm of GMN (Li et al, 2019). The novel part would be primarily in post-processing normalization (described in 3.1) for the matching matrix and seems to also be applicable to other NNs (for example, GAT?). The second part GSE to get an explicit subgraph also seem to be applied independently to the first part. We can see that combining these two parts worked, but it is unclear how each component contributes to the performance gain compared to any possible alternatives of each part.
I understand that MCS detection from a matching matrix (and node state vectors) is not exact if we just use Hungarian-like linear assignment problem (LAP) solvers for a submatrix obtained by a simple thresholding, but both post-processing normalization and GSE parts (which brings the novelty) can be more carefully evaluated through some 'ablation studies' using some simple alternative substitutes.