In the graph edit distance (GED), we are looking to find the cost of modifying one graph $G_1$ to another graph $G_2$. Is the sequence of operations that take $G_1$ from $G_2$ of interest in this problem? Or is it typically just the cost that is of interest?

I realise that finding the operations is likely to be one way to obtain the GED, but I am curious to know whether people are actually interested in these operations? For instance, if a heuristic could simply find(/approximate) the GED without returning the operations (for instance, machine learning based methods have been used to estimate the GED by comparing the distance in an embedding space of the two graphs) would this be considered as interesting as also knowing the operations?

To me personally it seems that having a heuristic that can actually obtain the operations required to modify $G_1$ to $G_2$ (that minimises the cost of doing so) would be the interesting part of the problem, but after having done some initial reading it seems that just estimating the GED is sufficient.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.