I'm looking to compare 2 unweighted directed graphs and get an (ideally differentiable) similarity score. Both graphs describe a trajectory in a 2d space.

The reference graph is a step by step guide to an end location. The nodes have a value which corresponds to a precise action such as forward 1m, left 30 degrees. The edges are only used to link steps together.

The comparison graph nodes on the other hand only contain directions rather than precision instructions (e.g. left, right, forward). Similarly the edges have no information.

While both graphs contain similar information,the comparison graph contains far fewer points (2-10x). I first tried reducing the reference graph to the same direction level by compressing multiple nodes of the same value together. This works somewhat, but leaves a lot to be desired. It is still too "low-level" to be directly comparable.

I'm in the process of evaluating edit distance (specifically a soft variant) and nDTW as possible candidates.

My questions are:

  1. What other metrics exist to compare graphs of this nature? I've looked at some slides and a survey on graph comparison and while these were helpful, I don't have enough intuition to choose between the methods they propose.
  2. Are there other ways of comparing these 2 sequences, besides treating them as graphs?
  3. Is there a community that might have a similar need? Like bio-informatics?