An improved invariant for matching molecular graphs based on VF2 algorithm

The molecular graph is a specific kind of graph. The classical method to solve the molecular graph matching problem is VF2 algorithm, where a heuristic is utilized to reduce the search space by analyzing the substructure of matched nodes. However, this heuristic invariant performs badly due to the strong similarity among some molecular graphs, thus the traditional VF2 algorithm has high time complexity. This paper introduces a novel heuristic invariant to effectively improve the computational efficiency, generated by the optimized circuit simulation method. We also conduct a series of experiments on PubChem dataset. The performance of the proposed algorithm is given by compared with the classical one.