Edit distance computational considerations

[bhavna-gopal]

The paper states that computing edit distance is manually expensive? What is used to compute edit distance? Isn't the cost of this compute trivial relative to an RL controller? Appreciate your help greatly!

[juice500ml]

Exact computation of graph edit distance is known to be NP-hard (https://en.wikipedia.org/wiki/Graph_edit_distance). We've checked some approximated versions, but never had any success, as those weren't usually for small-scale graphs like we're handling. For the exact ones, we've used the networkx implementations, and it is very CPU-intensive. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.similarity.graph_edit_distance.html#networkx.algorithms.similarity.graph_edit_distance