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: Graph and subgraph edit distance (GED and SED) are important mechanisms to measure the distance between graph pairs. However, it is NP-hard and thus hard for scalability. This paper proposes a framework based on the graph neural networks, named GREED, to learn the graph embedding for the edit distances. 

Unlike the previous methods, GREED is able to preserve the essential theoretical properties (e.g., triangle inequality, non-negativity, etc.) of the MED as the metric distance function, and also can easily be adapted to SED. Therefore, the embeddings learned from the GREED are indexable, significantly improving query time. 

Comprehensive experiments are conducted to validate the proposed method. GREED outperforms state-of-art methods across ten real-world datasets up to millions of edges and is faster than other methods. 

strengths_and_weaknesses: Strengths:
First of all, the paper illustrates the motivation, problem, and previous works' limitations clearly. The paper's overall organization is good and easy for readers to follow. The authors open the source code, which is good for reproduction and will benefit the entire community. 
Secondly, the proposed method (GREED) can learn the theoretical properties-preserved graph embedding. And the author provides the math proof for it.
Thirdly, the learned embedding is indexable and pair-independent, which is essential for scalability and fails most of the previous works in the literature. In this aspect, the author not only provides the neural networks-based model but also details of query algorithms.
Last but not least, lots of comprehensive experiments and discussions are conducted to validate the GREED, including prediction accuracy, method efficiency, scalability, and generalizability.

Weaknesses:
1. The main concern I have is the novelty of the design of the neural network and the corresponding ablation study (section 4.5). It seems that the second and third strengths above (i.e., preservation of GED's theoretical properties) are mainly from the last layer (i.e., GED and SED prediction functions F). In other words, the paper doesn't have theoretical insights into the choice of siamese architecture and the GNN component. In this case, the ablation study is important to support the claim. However, from Fig. 3(i)~3(k), the model component design seems not convincing (i.e., the green line is not the best). To better understand it, I raised a couple of questions in the "Questions" box. 
2. Meanwhile, some writing parts can also be improved. For example, 
(1) The table's index is unclear. There are two different "table 1" on page 7 and 15, respectively.
(2) Figure 4d should be "Dblp" instead of "IMDB". 
(3) Try to put the figure (tables) and corresponding text on the same page for reading-friendly purposes.

questions: The following questions are mainly related to section 4.5:
1. It seems that all the ablation studies are related to the SED based on the caption of Fig. 3, do you have any experiments with the GED? Those experiments can also help to test the consistency of the results. 
2. From Fig. 3(i)-(k), we can observe that the blue line (Greed-NN) has a better performance on PubMed and CiteSeer datasets. What is the possible reason for it?
3. Does the Pre MLP matter since you use the one-hot encoding? Meanwhile, a bit larger problem is whether all the component in Figure 2(b) is necessary. In other words, can we directly use GIN (or other GCNs) to replace Figure 2(b)?



limitations: In the paper, the authors have explicitly or implicitly pointed out a couple of limitations: (1) not considering the edge labels; (2) not having well generalizability. 
For limitation (1), I encourage the authors to explore and take advantage of some edge-related GCN models. For limitation (2), I suggest the author do more analysis of the dataset properties to find the reason for the poor generalizability. For example, is it caused by the structure domain shift (e.g., small world, scale-free property, and so on) or feature difference?

To best of my knowledge, there is no potential negative societal impact.
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: In this work, the authors design a novel siamese graph neural network GREED which can learn graph (GED) and subgraph edit distances (SED) in a property-preserving manner. 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 through empirical results demonstrate that the proposed approach works well as well as is significantly faster compared to the other baseline approaches.
3) The authors via using a siamese graph neural network which utilizes shared parameters to embed both the query and target graphs respectively are able to reduce the model parameters as well as the training time significantly.

Here are the main weaknesses of the current work :
1) The proposed approach has limited novelty factor. 
2) The authors do not seem to compare their work with state-of-the-art recent approaches which could have been good baselines to compare against. More concretely, the authors do not cite and/or compare against the following state-of-the-art recent approaches i.e., GOTSim [3], NeuroMatch [4], Graph embedding network (GEN) [5], and IsoNet [6].
3) Some aspects of the paper lack details/discussion and the authors do not seem to have tried to experiment with different settings more before finalizing their approach. More concretely, the authors could have tried non-sharing of parameters between query and target graphs to see if it helps. Additionally, the authors could have experimented with alternatives for their Graph Isomorphism Network (GIN) module. Also why did the authors specifically choose sum pool rather than other pooling techniques. The authors could also have tried approximate nearest neighborhood (ANN) based approaches in their work. 

[3] Khoa D Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. pages 665–674, 2021.
[4] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprint arXiv:2007.03092, 2020.
[5] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pages 3835–3845. PMLR, 2019
[6] Indradyumna Roy, Venkata Sai Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. AAAI, 2022.
questions: q1) Why did you not cite and compare your approach against the following state-of-the-art recent approaches i.e., GOTSim [3], NeuroMatch [4], Graph embedding network (GEN) [5], and IsoNet [6] ?

q2) Did you try any other alternatives to siamese graph neural network settings i.e., non-sharing of parameters between query and target graphs to see if it helps ?

q3) Did you try any alternatives to the Graph Isomorphism Network (GIN) module ? 

q4) Why did you use sum pool specifically ? 
limitations: The authors list just one limitation 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: In this work, the authors propose a neural framework to learn two well established metric, GED and SED, for graph similarity computation. By designing a siamese graph neural network to learn GED and SED in a property-preserving manner, the authors also show that the learned functions can guarantee to be a distance metric. Experiments demonstrate the effectiveness of the proposed framework in terms of accuracy and efficiency.
strengths_and_weaknesses: ### Strengths
1. The idea to unify GED and SED in one learning manner is kind of interesting.

2. The proposed framework is reasonable to approximate GED and SED.

3. The experiments are comprehensive.

### Weaknesses
1. There have been many works, as mentioned by the authors, on learning graph-based similarity metrics by GNN, thus in general, the novelty of this idea is limited. It is straightforward to include SED into the framework.

2. Though useful, the proposed GNN framework is not novel, which have been proposed in previous works. Especially, the motivation to use Siamese GNN is not clear.

3. The presentation of this work need improvements:

    a) The title ``learning graph distance functions’’ is kind of overclaimed, since the work only learns for graph edit distance, while there are other distances, like maximum common subgraph.

    b) The content of Section 2 is a bit too much, since most of them are established knowledge, not proposed by the authors. The authors can shorten Section 2 by moving some materials to appendix. Moreover, it would be better the authors give the references for GED, SED, and the properties.

    c) In Section 4, the ref of some tables are wrong, e.g., the text following ``4.2 Prediction Accuracy of SED and GED`` and ``4.3 Efficiency`` are all Table 2a and 2b, which is confusing

    d) In Section 4.6, the authors mentioned Table 3a is not found in the paper. 

    e) In the Readme of the code, the submission information is still KDD 2022. In fact, I think this is the reason that the table references are messy in the paper. The authors should carefully proofread the paper for NeurIPS submission.

questions: Besides the above weakness, one more question is from Section 4.5:

From Figure i-k, we can see that Greed-NN shows better performance compared Greed in two out of three datasets, i.e., on PubMed and CiteSeer. The authors should give some analyze of this phenomenon, which is very important to justify their claimed inductive bias.

limitations: None
review_title: null

Meta-review: metareview: The paper studies an important problem of computing distance functions across graphs which is NP-hard to solve in the worst case. The author provide a theoretical analysis of certain properties of the algorithm, and show its relevance in practice. The reviewers pointed out some weakness, but the rebuttal helped resolve some of those.  Please address those comments for the camera ready version.

The paper has weak accept votes, but in light of the significance of the topic, I also lean toward accepting the paper.
confidence: Certain
Decision: Accept