Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The main contribution of the paper is to propose a new teacher-student framework for efficient graph similarity computation. Different from existing early-fusion models that directly output a similarity score for two input graphs, the proposed framework uses such model as a teacher to teach a student model for fast embedding training and efficient graph similarity computation.
main_review: Pros:

- The teacher-student framework for graph similarity computation has several advantages. First, it can collect the individual graph embeddings from the joint embeddings of the two graphs. Second, the student model can distill knowledge from the pretrained teacher model and capture the well learned embedding distance in the teacher model. Third, the teacher-student framework prevents pre-computing the graph embeddings. Overall, the proposed framework is practical and technically sound. The student model can achieve a trade-off between speed and accuracy for graph similarity computation. 

- The presentation is good and the paper is easy to follow. Experiments on four benchmark datasets demonstrate the effectiveness of the proposed model.


Cons:

- In my view, some contributions of this paper are over-claiming. The authors say that they "speed up the prior art by 65x on the benchmark AIDS data." According to the results in Table 3,  it is 9.672/0.148 = 65.35. However, the 0.148s is only the inference time and does not include the time for pretraining the teacher net. It may not be fair to compare the inference time of the offline-stored student model against other early-fusion models. Besides, the reported data for the baselines *Hungarian* and *GENN-A* seems wrong. As reported in Table 3 of the GENN-A paper, their inference time is less than 1s rather than the reported more than ten seconds. So, I think the experimental results cannot well support the claim that the proposed model can speed up 65x. Perhaps, I have some misunderstandings here. So, I would be grateful if the authors could give more explanations to clarify this issue.

Typos:

- Line #126: "In specific, the edge linking the a pair of nodes including..." -> "In specific, the edge linking a pair of nodes including..."

-- After rebuttal --

- Thanks for the responses to address my concerns regarding the inference time. 
- I would like to leave my score unchanged.
limitations_and_societal_impact: Please give more details on inference time comparison because it is a key experiment.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper authors proposed a method to solve subgraph similarity problem using graph neural network. They proposed a knowledge distillation based technique to distill knowledge from a slow early fusion based model to a faster student model which improves the speed of the inference. 

main_review: Originality: 

The work is a novel combination of techniques like Graph Isomorphism Network, slow Early Fusion model, faster Inference model, Knowledge Distillation between the slow model and the fast model. I specially liked the design of the two models for knowledge distillation.

Quality: 

The submission seems technically sound. Claims are generally well supported. One analysis I missed was, why the GENN-A* outperforms this model by a lot specially in AIDS dataset. Any intuitive analysis about this outperformance would have made the paper stronger. I still feel this direction of work is important, but it would be good to know whats missing in the work to make the work better.

I liked the ablation analysis of different parts of the model, 

Also Inference time improvement is impressive, but can we improve the accuracy more even if we use similar times to the other methods especially GENN-A*. I feel like we need to analyze the trade off between time and accuracy in this work. Especially can we design a more accurate teacher model which can use more time/memory to be competitive with GENN-A*.

Clarity: 

The submission is clearly written and seems well organized. There are some typo like "graph convectional network" in line 41. But the work was easy to read and understand.

Significance: 

I think this is a very important problem to solve in this area. It should be impactful work for researchers in this domain. Even though it does not beat the state-of-the-art in all cases, its still a novel way to model the problem.


limitations_and_societal_impact: Did not find the section
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a new method for computing graph similarity efficiently and approximately using graph neural networks. A novel attention-based neural network is proposed for combining the embeddings for the two input graphs. A novel way to compute graph similarity faster is proposed based on embedding decomposition and applying knowledge distillation to obtain a fast model from a slow model. Experiments on four graph datasets demonstrate the effectiveness and efficiency of the proposed method.
main_review: Originality: The task addressed in the paper is graph similarity computation (GSC), which can incorporate several hard-to-compute metrics such as GED, MCS, etc. The proposed method contains a novel Embedding Fusion Network (EFN) and a novel way to apply knowledge distillation to the task of GSC. It is clear how the proposed model is different from previous works, and the important previous works are adequately cited and compared against in the experiment.

Quality: The submission is technically sound with claims relatively well supported by experimental results. The authors also list several limitations of the work in the supplementary material. However, I recommend the authors testing the methods on larger graph datasets and more graph similarity metrics to better support the claims.

Clarity: The submission is clearly written and well organized.

Significance: The paper indeed points out a potentially very promising direction of computing graph similarity in an efficient way, ie using knowledge distillation. The idea of learning both a slow model and fast model on its own is not new but is a very interesting and promising direction, and is relatively underexplored in the graph deep learning domain. I can foresee future researchers could build upon this idea.



limitations_and_societal_impact: There are several things that could further improve the quality of the work:

1. The authors use four benchmark datasets, but given the high standard of NeurIPS and the relatively small sizes of the four datasets, I strongly recommend the authors using larger datasets in terms of both the number of graphs and the average number of nodes. Specifically, the authors do not mention the detailed statistics of the datasets, but by checking with previous works, it seems the largest dataset contains a few hundreds of nodes on average. Scaling to graphs of 1K, 10K, 100K, and even 1M nodes will show the strengths and potential limitations of the proposed method better. This is especially important since one key contribution is the fast model learned through embedding decomposition and knowledge distillation. 

The issue of dataset being small is also seen from Section 4.4 and Table 3, where the authors show the average inference time on AIDS. AIDS only contains graphs of <= 10 nodes, and using this dataset to demonstrate how fast the student model runs is fine, but if using a very large graph dataset of more nodes on average, the speed-up gained by the fast model can be more significant.

2. The authors mention several graph metrics in Section 2.1, but only GED is used in the experiments. The authors should consider testing the methods on other metrics such as MCS.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper tackles the problem of graph similarity computation (GSC). The key insight of this paper is that to better model the problem of GSC, early and extensive graph feature fusion is needed, which is harmful to model efficiency. To address this issue, the authors propose a knowledge distillation solution that drops all early fusions. This allows the regression models to take in only the embeddings, which can be pre-computed, and thus saves time. Experimental evaluations indicate that the proposed framework achieves good performance and is fast in inference. 
main_review: Overall I like this paper. The paper is based on insightful observations about feature fusion and efficiency, and the proposed technical solution, although not completely new, is sound. The experimental evaluations are extensive. `

**Strengths**: 
- **Clarity**: The paper is in general easy to follow. 
- **Experiments are extensive**. I specifically appreciate the extensive ablation studies on the design. 
- **Sound technical solution**. The technical solutions are based on insightful and realistic observations. 

**Weaknesses**: 
- **Somewhat lack in novelty**: As attention, multi-level graph feature fusion, and KD are all existing techniques, the technical solution seems a little short of novelty, although indeed, it is technically sound.
- **Unfair comparison of inference time**. Since the query graphs may come at any time and may be arbitrary new graphs, I think the comparison of inference time in Table 3 is not very fair, as for completely new query graphs, you still need to first compute its embedding. 

**Minor comments**: 
- Line 173, 'a node-wise attention to aware of...', to aware of -> to be aware of
- Line 174, $h = \sum_{n=1}^N \sigma(x^T_ncx_n)$, should it be $\sigma(x^T_nc) x_n$?
- The notations through Sec. 3.2.2 are confusing. For example, $h_{ij}^{all}$ and $\mathbf{h}_{ij}^{all}$ are interleavingly used.  Please consider unifying them. 
- Line 220-221, consider revising the notations, as the $E(\cdot, cdot, cdot)$ repeats too many times. 
- Eqn 7, I suppose that Huber loss is a binary function, but why is $l_\delta(\phi_D(h_{Ab}^T, h_{aB}^T), h_{Ab}^S, h_{aB}^S)$?
- Sec. 4.1.2, "matrix"->"metric". 

limitations_and_societal_impact: They are properly addressed.
review_title: null

Meta-review: This paper proposes a new teacher-student framework for efficient graph similarity computation. The student model decouples the interaction of two graphs learned in teacher model into two separate representation vectors, which can speed up the inference significantly. The authors’ rebuttal is general well written, and has provided new experimental results requested by the reviewer.  The reviewers have concerns on the novelty, as the main techniques are adapted from existing work. But the application of knowledge distillation for similarity computation itself is novel, and the design is smart and suits the inference need very well. The results are significant. Therefore, I recommend acceptance.
Decision: Accept (Poster)