MATA*: Combining Learnable Node Matching with A* Algorithm for
  Approximate Graph Edit Distance Computation
Junfeng Liu Min Zhou Shuai Ma Lujia Pan
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 (GNNs) and A* algorithms, which models from the
perspective of learning to match nodes instead of directly regressing GED.
Specifically, aware of the structure-dominant operations (i.e.,node and edge
insertion/deletion) property in GED computation, a structure-enhanced GNN is
firstly designed to jointly learn local and high-order structural information
for node embeddings for node matchings. Second, top-k candidate nodes are
produced via a differentiable top-k operation to enable the training for node
matchings, which is adhering to another property of GED, i.e., 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 show the superiority of MATA* as it significantly
outperforms the combinatorial search-based, learning-based and hybrid methods
and scales well to large-size graphs.