Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper provides a reinforcement learning method for subgraph matching problem. Given a query graph, they attempt to find the subgraph from a large graph that matches a query graph. Then the paper compare the underlying method against several baselines on real world datasets.
strength_and_weaknesses: Strengths:
+ Important problem
+ Intuitive approach

Weakness:
- Lack of well known baselines
- Lack of novelty
clarity,_quality,_novelty_and_reproducibility: The paper is written clearly. However, the quality of the experiments are poor. 
The code is not given with the paper. Also, novelty of the paper is limited as it follows a very close approach with https://arxiv.org/abs/2002.03129.
summary_of_the_review: I have two key concerns with the paper. 
First, lack of powerful baselines. The paper acknowledges that most baselines are supervised learning methods. Thus, they adapted it into the RL method, which we appreciate. In this context, there are two powerful baselines which are never used:
(1) https://arxiv.org/abs/1904.12787 and
(2) https://ojs.aaai.org/index.php/AAAI/article/view/20784

Second, I really did not find any significant difference (of course there is some difference but they are not significant) from the approach adapted in https://arxiv.org/abs/2002.03129.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the subgraph matching problem to perform a subgraph isomorphism check between a query graph and a large target graph. The authors attempt to solve the solution and reward sparsity issues by designing an encoder-decoder neural network and look-ahead loss function based on reinforcement learning. Experiments conducted on six datasets show the effectiveness.
strength_and_weaknesses: Strengths:
1. Detailed preliminary introduction to help the readers to understand the pipeline.
2. The problem is not easy and deserves more attention.
3. The proposed method is technically sound. 

Weaknesses:
1. As far as I know, the related work for learning-based methods for subgraph matching is incomplete.
2. The paper contains many notations and is hard to follow. Some preliminary knowledge could be moved to the Appendix because the main focus of this paper is on neural design.
3. The methodology contribution is limited. Several works have adopted the idea of designing the encoder to encode two graphs and the design of the decoder is not novel.

clarity,_quality,_novelty_and_reproducibility: 1. The authors claim that heuristics-based solvers often fail to find any solution. Is the proposed method still based on heuristic-based ordering to select Ut?

2. The related work is incomplete. Several related works should be discussed and probably need to be compared.

a. Consistent Subgraph Matching over Large Graphs. ICDE 2022

b. Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching

c. Interpretable Neural Subgraph Matching for Graph Retrieval. AAAI 2022:

d. Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching. AAAI 2022

3. The authors claim that aggregating nodes from Vq to obtain the state representation can address the challenge (2). Does it mean the NP-hard task can be solved?

4. The state includes two graphs; its representation is only learned from the query graph. The motivation is not clear. How does the proposed method ensure the information on the target graph can be completely preserved?
summary_of_the_review: The paper proposes a reinforcement learning framework to solve the subgraph matching problem and designs an encoder and a decoder. The paper is technically sound but missed several related works and is not easy to follow. Also from my perspective, the methodology contribution is limited.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a learning based method for subgraph matching, using a graph neural network-based encoder-decoder architecture, and a reinforcement learning strategy. The GNN consists of two main modules: intra-graph message passing for modeling graph structures, and inter-graph message passing for query-graph matching. Furthermore, a look-ahead loss is formulated to supplement training signals.
strength_and_weaknesses: Strengths:
1. The idea of inter-graph message passing for matching is novel to me. Existing GNN architectures only focus on the intra-graph counterpart.

2. The use of reinforcement learning can reduce or eliminate labeling effort. 



Weaknesses:
1. There is a large body of literature on the related subgraph isomorphism counting problem. In many applications, the profile of subgraph counts can sufficiently characterize a graph and it is not necessary to find all or most instances of the query.  Discussing some case studies and example applications could be useful to motivate why it is necessary beyond counting. 

2. The proposed model has high initial overhead. The methods only show significant advantage after a few mins. However, in many cases it might be important to get a few matching instances fast rather than getting many instances later on. 

3. Some parts are not well explained in detail.
- 3.1: "We define our reward as R(+) = 1 if the subgraph is fully matched and R(−) = 0 otherwise." Do you actually mean the "current" subgraph is fully matched?
- 3.1: "Therefore, after the search, we collect the positive training signals at each state as all the node-node pairs (u, v) that lead to a solution" I'm not clearly how this is exactly done. A step-by-step explanation might be useful.
- 3.2.1: How are the mapping M, M' are constructed? Again, a step-by-step instruction might be clearer.

Minor issues:
The ablation study is important and should be moved to the main paper. 
clarity,_quality,_novelty_and_reproducibility: The paper presents some novel ideas. Certain parts need to be better explained. Practical impact (motivation/applications/results) may not be as significant as one would have hoped.
summary_of_the_review: Overall I think the weaknesses slightly overweigh the strengths.

---

Update: I'm largely satisfied with the responses, except for the initial overhead. The cost of executing NNs is part of the cost, which cannot be simply discounted. Overall, i will upgrade my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors presented a neural search method NSUBS to solve the subgraph search problem. The key idea is to pass information between the query and a local candidates pool at every search step to optimize the search. 
strength_and_weaknesses: The paper is well-executed and easy to follow. All parts are clearly presented and convincing. Experiences are thoroughly done. 
The key contribution also involves the dynamic message passing + a look-ahead loss to guide the RL to find the optimal order of search. 

1. It is great that the authors provided time complexity and empirically validated it via experiments. But It is unclear the training complexity. Especially with the look-ahead loss, do we have to add up many future steps to compute the loss at every step?
2. It would be helpful in the experiments the authors could provide a total time for training the learnable models, including this model. For models that often get stuck in a local minimum and often do not improve further after the first 20-60 seconds (fig 2), would it be fair to restart them with some different random seeds and repeat them until 5min? 
3. I was a bit confused: does NSUBS also follow a general DFS + backtracking approach? If so, wouldn't it suffer from the local minimum problem as well? 
4. The authors claimed NSUBS works better at large query graphs. But the results section doesn't provide further performance stratifications on queries w. different sizes. It would strengthen the paper if the readers can see some breakdown numbers to better understand this claim. 
5. Related to 4, it would be helpful if the authors could have some effort into the model interpretation. For example, show an actual search trajectory and show how the NSUBS modifies the local candidate list to speed up and optimize the search. 
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow. The quality is good except I would love to see a few more experiments. Novelty is fair. 
summary_of_the_review: I am willing to increase my score if the authors could address my questions and provides some more fair comparison and insights/limitations of the model.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the subgraph matching problem where one needs to determine whether a query graph appears in a given target graph. The paper proposes a graph neural network-based encoder-decoder architecture combined with a reinforcement learning strategy. The GNN consists of two main modules: intra-graph message passing for modeling graph structures, and inter-graph message passing for query-graph matching. A look-ahead loss is used to supplement training signals.

Through a reviewer-AC meeting, reviewers point out several main concerns for the paper. First, there are many related works missing in their submitted version, which is pointed out by 3/4 reviewers in their reviews. Secondly, some powerful baselines are missing such as GMN. Reviewers point out that GMN is actually very hard to beat and there is no excuse to not compare. Thirdly, the paper is incremental to an existing work GLSearch. While I appreciate the hard work the authors did during the rebuttal, at the current stage I decided to respect the reviewers' opinions and recommend a rejection.
justification_for_why_not_higher_score: The reasons are stated in the meta-review. Lack of related works and strong baselines, incremental to an existing work. Though the authors did hard work during the rebuttal, their responses did not convince the reviewers in the end.
Decision: Reject