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: This paper presents a novel way to compute graph similarity, in particular graph edit distance (GED). The key insight is a proposal of necessary conditions under optimal permutation (i.e., eq. (3) and eq. (4))) that lead to the computation of GED. Based on the insight, a neural model is introduced, critically reducing the computation burden from node-to-node similarity computation (quadratic w.r.t number of nodes) down to node-to-graph similarity computation (linear w.r.t. number of nodes). Experiments validate the effectiveness and efficiency of the proposed method.
strengths_and_weaknesses: Strengths
- Under the proposed necessary conditions in Sec. 3, the computation of GED is reduced to node-to-graph level computation. It greatly reduces the traditional neural methods that take node-to-node level computation.
- The model design is technically reasonable and correct.
- Experiments are well designed and sufficiently show that the proposed methods establish new SOTA results while using significantly less running time. Ablation studies further validate the value of each component.
- The paper is well structured and easy to follow.

Weaknesses: One thing that is unclear is the motivation in Sec.3. Authors propose how they arrive at the necessary conditions for computing GED. However, the derivation involves multiple steps and is somehow conceptual, e.g., quoted from the paper: "a necessary condition is that the distance between $f_θ(A_i [k])$ and $f_θ(\pi^* (A_j )[k])$ is minimized for all $k \in {1, \ldots, N}$." It would be more convincing to include formally mathematical derivations to obtain these necessary conditions.
questions: N/A
limitations: Yes, the authors have adequately addressed the limitations and potential negative societal impact 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: This paper proposes a novel framework, named ERIC, for graph similarity computation. The first technical contribution is to analyze GED in embedding space and further approximate the ground-truth GEDs with $\gamma_{i}$, $\gamma_{j}$ and $\||\gamma_{i}-\gamma_{j}\||_{2}$. Based on the analysis, the authors introduce Alignment Regularization (AReg) into model training. In addition, the authors discuss the necessity of multi-scale GED discriminator when training GNN encoder. Overall, the graph similarity computation framework ERIC consists of AReg and Multi-Scale GED Discriminator as two submodules.
strengths_and_weaknesses: **Strengths**:
1. This paper is well structured, clearly written and easy-to-follow. In section 3, the authors first theoretically investigate into GED in embedding space. The corresponding conclusion supports the justification of AReg in section 4.
2. Approximating the ground-truth GEDs with $\gamma_{i}$, $\gamma_{j}$ and $\||\gamma_{i}-\gamma_{j}\||_{2}$ is novel and reasonable. This method not only reduces the computational and memory cost, but also simplifies the matching process and thus makes it easy to implement.
3. Figure 4 provides an intuition that multiple similarity discriminators are likely to provide more useful information to reflect GED. It is a good practice.
4. The authors conduct extensive experiments and illustrate the results clearly in the paper and the supplementary material.

**Weaknesses**:
1. The authors claim that *diverse similarity discriminators may provide complementary information to reflect GED more accurately*. However, they only discuss and use two kinds of similarity discriminators, i.e. NTN and $l_{2}$ distance, in the paper. 
2. It is pointed that minimizing $\gamma_{i}$, $\gamma_{j}$ and $\||\gamma_{i}-\gamma_{j}\||_{2}$ is the necessary condition of the optimal $\pi$. But since it is not a sufficient condition, more evidence is required to make the approximation justified.
questions: As mentioned in **Weaknesses**, I suggest the authors to:
1. Take more types of discriminators into account;
2. Analyze the accuracy of this approximation method;
limitations: I think the applicability and practicality of the proposed method is not low, but the authors describe little about its social value and impact. Nor do they mention the limitations of the paper. It would be better to describe more about social impacts or limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the efficient graph similarity computation problem. The core is to compute graph edit distance, which is an NP-hard problem. Recent efforts resort to graph network for approximation. However, the existing node-level matching module is usually computationally expensive. This work shows that the node-level matching is not necessary. Instead, the authors propose a node-graph level correspondence as a regularization term, and inject it into the standard training framework. The experimental results show that the proposed regularization term performs competitively in both matching accuracy and inference speed. 
strengths_and_weaknesses: Strength

-This paper is mostly well written. I like the discussion in the motivation section, from which the proposed formulation is derived.

-The proposed regularization term AReg, capturing the node-graph interaction between two graphs, is intuitive.

-The experimental results suggest the proposed AReg outperforms other baselines in both accuracy and inference speed. 


Weakness 

-Some technical points are unclear in terms of presentation. (see questions)

-Ablated results suggested that the proposed AReg has limited contribution to the final performance.

-Missing key parameter analysis on $\lambda$. It is unclear to me how $\lambda$ is learned.

questions: -Line 40, it is stated that “since cross-graph interactions are ignored, …”. While EGSC seems have the early fusion layers which aim to learn the cross-graph interaction. Please clarify this sentence. 

-Line 209, $\lambda$ is a trainable parameter. Please elaborate on how it is trained. If $\lambda$ is prefixed, please provide the sensitivity analysis on it.

-Table 4 in supplementary, it seems that the performance gain by AReg is limited. For instance, in AIDS700, ERIC (w/o AReg) on mse/$\rho$/P@10 are already 1.573/0.886/0.652. And it already achieves the best performance in p@10 compared with other baselines. Why ERIC w/o AReg can beat other baselines like EGSC?

Also, ablation study is an important analysis, deserves to be put in the main text. I suggest the authors better organize the content to fit this part in the main paper.

limitations: The authors adequately addressed the limitations and potential negative social impact of their work.
review_title: null

Meta-review: metareview: Compute similarity between two graphs based on the graph edit distance (GED) is expensive. This paper proposes a learnable way to infer GED quickly. The propose method has two stages, in the first stage, the GNN encoder capture underlying alignment information between pair-wise graphs; in the second stage, it uses the learned encoder to reflect the exact GED value between two graphs. 

Questions raised by reviewers, i.e., on motivations /  types of discriminators /  accuracy of this approximation method / sensitivity of lambda, have been addressed during the rebuttal.  Authors are encourage to reflect these changes in the final version.
confidence: Certain
Decision: Accept