Currently, the most efficient exact answer is Depth-First Graph Edit Distance (DF-GED), from An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems. An implementation exists in Python's networkx library.