Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

Strong points:

--- The paper deals with an important problem, and the overall learning-based formulation and solution look very interesting.

--- 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.

--- The ablation study is interesting and demonstrates that the chosen architecture of GLSEARCH has consistent behavior.


Weak points:

--- 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?

--- 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.


Typos:

--- Page 4, first paragraph: *F*or MCS, …
--- Caption of Table 3: *Ablation*

review_title: Learning-based formulation of the MCS problem. Interesting approach based on GNNs and RL. Experiments on larger graphs would be interesting to consider.

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

Strengths:
1.	The motivation of this paper is clear and interesting.
2.	The authors conduct many experiments to demonstrate the effectiveness of the proposed method.
Weakness:
1.	The 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. 
2.	In Figure 1, what’s the difference between 01 and 10?
3.	In equation 2, what operation does INTERACT stand for? 
4.	The 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.
review_title: This paper proposes GLSEARCH, a Graph Neural Network based model for MCS detection, which aims to search for the maximum common subgraphs between two input graphs. 

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

- 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. 
- 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. 
- Are there some interpretable heuristics that you can derive by studying the policy of your algorithm? 
- 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? 
- 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?  
- 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.

Overall I found the paper to be interesting, but there are some non-trivial issues that need to be better addressed. 
review_title: Bringing together RL and GNNs to guide search for MCS

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