This work presents a two-stage neural architecture for learning and refining structural correspondences between graphs. First, we use localized node embeddings computed by a graph neural network to obtain an initial ranking of soft correspondences between nodes. Secondly, we employ synchronous message passing networks to iteratively re-rank the soft correspondences to reach a matching consensus in local neighborhoods between graphs. We show, theoretically and empirically, that our message passing scheme computes a well-founded measure of consensus for corresponding neighborhoods, which is then used to guide the iterative re-ranking process. Our purely local and sparsity-aware architecture scales well to large, real-world inputs while still being able to recover global correspondences consistently. We demonstrate the practical effectiveness of our method on real-world tasks from the fields of computer vision and entity alignment between knowledge graphs, on which we improve upon the current state-of-the-art.
This paper proposes a two-stage GNN-based architecture to establish correspondences between two graphs. The first step is to learn node embeddings using a GNN to obtain soft node correspondences between two graphs. The second step is to iteratively refine them using the constraints of matching consensus in local neighborhoods between graphs. The overall refining process resembles the classic graph matching algorithm of graduated assignment (Gold & Rangarajan, 1996), but generalizes it using deep neural representation. Experiments show that the proposed algorithm performs well on real-world tasks of image matching and knowledge graph entity alignment.
The paper is interesting and has some good potential but lacks some important evaluations and analyses. My main concerns are as follows. 
1) The consensus in the second stage is crucial? 
As the title shows, the main technical contribution lies in the second stage of consensus inducing. But, for the real tasks, in the experiments, the gain by the second stage is not significant or often negligible (L=0 vs. L=10 or 20  in Table 1,2,3). The results of the first stage (L=0) already give better results than all the baselines in many cases, so that most gains appear to come from the usage of GNNs for representation. This makes the major contribution of this work less significant.  I hope the authors justify this. And, I guess that's maybe because the consensus information may also be induced in the first stage by matching nodes with relational presentations learned using a GNN. To see this, the authors may run the second stage only without the first stage. 
2) Comparison to the graduated assignment (GA) process
As discussed in 3.3, the proposed neighborhood consensus can be viewed as a generalization of GA of Eq.6 with trainable neural modules. But, it's not actually shown what is the gain by this generalization. This needs to be shown experimentally by substituting the second stage by GA process.  
3) Robustness to node addition or removal. 
All the experiments look assuming only edges are varied. Is this algorithm robust to node addition or removal, occurring in many practical graph matching problems? This needs to be also discussed.   
======================================
The rebuttal succeeds in addressing most of my concerns so that I upgrade my initial rating to weak accept. I hope all the points in the rebuttal are included in the final manuscript.