Before revision:  Our model uses an exploration tree to extract subgraphs in two graphs one node pair at a time , and is trained to optimize subgraph extraction rewards via Deep Q-Networks. A novel graph embedding method is proposed to generate state representations for nodes and extracted subgraphs jointly at each step . Experiments on real graph datasets demonstrate that our model performs favorably to exact MCS solvers and supervised neural graph matching network models in terms of accuracy and efficiency .
After revision:  Our model uses an exploration tree to extract subgraphs in two graphs one node pair at a time . Instead of using heuristics, we propose a novel GNN-based Deep Q-Network (DQN) to select the node pair, allowing the search process faster and more adaptive. To further enhance the training of DQN, we leverage the search process to provide supervision in a pre-training stage and guide our agent during an imitation learning stage . Experiments on real graph datasets demonstrate that our model performs favorably to exact MCS solvers and supervised neural graph matching network models in terms of accuracy and efficiency .