Title: MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation. Abstract: Graph Edit Distance (GED) is a general and domain-agnostic metric to measure graph similarity, widely used in graph search or retrieving tasks. However, the exact GED computation is known to be NP-complete. For instance, the widely used A* algorithms explore the entire search space to find the optimal solution which inevitably suffers scalability issues. Learning-based methods apply graph representation techniques to learn the GED by formulating a regression task, which can not recover the edit path and lead to inaccurate GED approximation (i.e., the predicted GED is smaller than the exact). To this end, in this work, we present a data-driven hybrid approach MATA* for approximate GED computation based on Graph Neural Networks and A* algorithms, which models from the perspective of learning to match nodes instead of directly regressing GED. That is it leverages the learned node matchings to prune unpromising search directions of the A* algorithm. Specifically, aware of the combinatorial property of structure-dominant operations (i.e., node and edge insertion/deletion) in GED computation, a structure-enhanced Graph Neural Network is firstly designed to effectively learn powerful node embeddings w.r.t. node matchings. Based on this, the pairwise node similarity matrix is next built. Second, top-k candidate matching nodes are produced from the similarity matrix which is adhering to the combinatorial property of multiple optimal node matchings. Third, benefiting from the candidate nodes, MATA* only performs on the promising search directions, reaching the solution efficiently. Finally, extensive experiments demonstrate the superiority of MATA* as it significantly outperforms the combinatorial search-based, learning-based and hybrid approaches and scales well to large-size graphs.