Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors propose LMCES and LMCCS, which are late interaction neural architectures for MCES (counting the number of common edges) and MCCS (the maximum common connected subgraph) based graph retrieval respectively. Additionally the authors propose XMCS (cross-MCS) which is an early interaction model that works well for both MCES and MCCS based graph retrieval. The authors demonstrate the efficacy of their approach via empirical results.
strengths_and_weaknesses: Here are the main strengths of the current work :
1) The authors focus on graph similarity measurement which is a very important problem in the graph ML community.
2) The authors propose both early and late interaction models for determining the MCES and MCCS, via introducing a relaxation to the node alignment matrix between query and corpus graphs.
3) The authors demonstrate the efficacy of their approach via exhaustive empirical study using seven diverse datasets and six state-of-the-art late interaction baseline models.

Here are the main weaknesses of the current work :
1) The novelty factor of the proposed approaches is somewhat limited. 
2) The authors should have included more results, including those related to the training/inference times for the different baseline models. Currently it is hard to compare whether the gain in performance is matched by the potential training/inference latency issues.


questions: q1) why did you not include results related to to the training/inference times for the different baseline models along with the proposed approaches ? 
limitations: The authors share multiple limitations of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes new neural network architectures for the task of graph retrieval (computing a score between a query graph and a corpus graph) tailored for the Maximum Common Subgraph (MCS) metrics. Two late interaction models and an early interaction model are proposed with trade-off in efficiency and accuracy. Experiments on seven real-world datasets show the superiority of the proposed models.
strengths_and_weaknesses: Strengths:
1. The proposed method is relatively novel, albeit heavily relying on the Gumbel-Sinkhorn (GS) network. 
2. Two variants in MCS definition are discussed (MCES and MCCS), which reflect the different needs of real-world applications.
3. The paper is well-written with enough details as well as code provided for reproducing the experimental results.

Weaknesses:
1. It is unclear how scalable the proposed methods are. First of all, the theoretical time and space complexity are not explicitly discussed, and thus the speedup compared with GMN is not explained from a theoretical point of well. Second, the statistics of the number of nodes and edges of the graphs in the seven datasets are not shown. Instead, the authors give a relatively vague description of how the graph pairs are generated in Section D, “Subsequently, we augment the seed query graph G′q , with randomly connected nodes and edges, which gives us the final query graph Gq for MCS computation.” How many nodes and edges are randomly added to the seed? What is the final size of the graph? This concern is of particular relevance given that exact MCS is NP-hard to compute, but the authors can generate the ground-truth MCS values “using the combinatorial formulations for exact MCCS and MCES,” raising the concern that whether the graph sizes are quite small so that even exact MCS computation is affordable. Figures 2 and 3 also show quite small graph pairs with ~20 nodes. Why would people use such approximate methods for MCS scores if the input graphs are small and the exact solvers can already handle them reasonably well? Without large graph experiments, the exact solver may be used as a baseline too, which is missing in the current experiments.
2. A minor concern is the applicability of the proposed models, since the models are specifically designed for MCS metrics, more specifically, MCCS and MCES. I agree that MCS metrics are already important and worth specific models designed for them, but it would be interesting to discuss the potential issues if the proposed methods are used for other metrics, e.g. GED, or domain-specific similarity scores. This would make the contribution and the scope of usage clearer.

questions: Please see above for questions.
limitations: The authors do not explicitly mention societal impact in details.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the neural graph retrieval problem. Specifically, it focuses on two similarilty scores, MCCS and MCES. Since exact computation is intractable, thus this paper designs neural functions to approximate MCES and MCCS. This paper proposes both early and late fusion of neural graph retriever, and experiments overs seven datasets show that the proposed approaches outperform baselines on both accuracy and speed. 
strengths_and_weaknesses: Strength: 

1. Although several research work has focused on neural information retrieval, few works on graph neural retrieval, an important but relatively underexplored problem. This paper fills in the gap. 
2. This paper proposed a simple neural graph retrieval method and works well on both accuracy and efficiency (significantly outperforms baselines) 
3. The paper is well-written, it's enjoyable reading it.

Weakness (more like suggestions, not really a weak point)

Since this paper proposes both early and late interaction approaches, a natural idea is to combine both approaches (e.g., hybrid approach). 
A straightforward approach is to start with late interaction to find some relevant graphs, then use early interaction to re-rank these graphs. The expectation is to find the optimal trade-off between accuracy and efficiency. 



questions: 1. Does different GNN architecture affect the results? 
2. Maybe add an experiment on hybrid interaction (start with late interaction, then interaction), and experiment on both accuracy and time. (see details in strengths/weaknesses).
3. Maybe add a few related works on neural information retrieval (e.g., dense retrieval)
limitations: Not addressed, but I do not think of any potential negative social impact.
review_title: null

Meta-review: metareview: This paper presents a neural method for the graph retrieval problem. Reviewers agree with the technical contribution of this paper, its empirical soundness, and the well written presentation. Discussions in rebuttal and additional experiments provided useful information and made this paper stronger. We suggest the authors update their next version according to reviewers’ suggestions and rebuttal discussions.
confidence: Certain
Decision: Accept