Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposed a graph net based approach for subgraph matching. The general idea is based on the graph matching network (Li et.al, ICML 2019) that computes the node embeddings of two graphs with co-attentions. The training requires the supervision of ground truth matching. During inference an iterative method with heuristic stopping criteria is used. Experiments on tiny graphs show better results than learning based baselines, but worse results than MCS solver.

Overall the paper is well motivated. However there are several major concerns with the paper:

1. Since it relies on the solver to provide training data, it might be hard to train on large graphs as there would be no cheap supervision. Also it seems that getting slightly faster but much worse results than the solver on small graphs is not that exciting. 

2. It seems there's a mismatch between training and inference. The inference method is done iteratively, where the Eq (6) is somewhat not clear to me: as this ||w1-w2|| criteria is not trained during training, it seems quite heuristic by doing so. 

3. I’m not sure why the two stop conditions are needed. One can easily check (incrementally) whether the added nodes are isomorphic.  

4. The graphs used in experiments are too small. 

Some other minor issues:

It would be better to define Y with Eq (1) and Eq (2) in the paper. There seems to be no explicit definition of Y. 


review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The authors proposed a novel method to find the Maximum Common Subgraph (MCS) of two graphs. I am familiar with the quadratic assignment problem (QAP) based graph matching and I am not very familiar with the MCS problem. 

The authors adopt Graph Matching Networks (GMN) for feature embedding, and then similarity matrix X can be generated by computing the similarities between the embeddings. The similarity matrix is then normalized using a similar way as the sinkhorn procedure in [1-3]. The Assignment matrix then can be given from X. Then a novel procedure, named Guided subgraph Extraction (GSE, which is considered as the main contribution of this paper), is used  to get an MCS from assignment matrix. Here the authors may consider a simple baseline, which is to use QAP to give the assignment matrix, and then run GSE to obtain the MCS. 

Overall the paper is well written, and the experiment is good and solid. 

Some suggestions:
The GCN based GMN might not be the best choice for graph embedding. The authors may consider stronger Graph Neural Networks such as DGCNN (used in [3]) or Message Passing Neural Network (used in [4] and [5]) as the graph embedding module in the future work. 

[1] Deep Learning of Graph Matching, CVPR18
[2] Learning Combinatorial Embedding Networks for Deep Graph Matching. ICCV19
[3] Deep Closest Point: Learning Representations for Point Cloud Registration. ICCV19
[4] Deep Graphical Feature Learning for the Feature Matching Problem, ICCV19
[5] Neural Message Passing for Quantum Chemistry, ICML17
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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.
review_title: Official Blind Review #3

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

Decision: Reject