Common Subgraph Based Distances

[tlarock]

There is a class of graph distances, largely published about in the late 90s/early 2000s, based on maximum/minimum common subgraphs. Should we implement these?

The following papers claim that the computation of the maximum common subgraph is a special case of the computation of edit distance:

1. On a relation between graph edit distance and maximum common subgraph
2. A graph distance metric based on the maximal common subgraph

These define some variants of common subgraph based distances:
3. A graph distance metric combining maximum common subgraph and minimum common supergraph
4. Graph distances using graph union

These papers are written by people more math-y than me. @leotrs (or anyone else!), could you take a look, specifically at 1 and 2, and comment on whether you think we should implement these?

[leotrs]

I confess I haven't read the cited papers, but I have Things To Say.

1. We should leave open the possibility for implementing any distance method, so let's keep this open
2. I don't think we need to worry about this for the time being (let's revisit after NetSci'19)
3. One thing we could think about for the time being - do these distances fit the two-step model outlined in Separating feature construction from calculation of distances #174 ? If not, what changes would we need to make to the library to include these?