Edit distance between 2 equal graphs is not 0.

[AndreudeDonato]

Hi

I was using the python library networkX to find isomorphic graphs, but I moved the code to Julia because I need efficiency. My problem is with the file edit_distance.jl.

Check this lines of code

graph = ((1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (4, 6), (5, 6))
graph2 = ((1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (4, 6), (5, 6))

G1 = SimpleGraph(6)
for edge in graph
    add_edge!(G1, edge)
end


G2 = SimpleGraph(6)
for edge in graph2
    add_edge!(G2, edge)
end

dist, _ = edit_distance(G1, G2)

The outputed distance is 3, but shouln't it be 0?
The two graphs are the same.

Thank you

[gdalle]

Hi!

Judging by the current implementation, this is expected behavior, because the default value for the subst_cost argument to edit_distance is the constant function equal to 0.5:

help?> edit_distance
search: edit_distance

  edit_distance(G₁::AbstractGraph, G₂::AbstractGraph)


  Compute the edit distance between graphs G₁ and G₂. Return the minimum edit cost
  and edit path to transform graph G₁ into graph G₂. An edit path consists of a
  sequence of pairs of vertices(u,v) ∈ [0,|G₁|] × [0,|G₂|]` representing vertex
  operations:

    •  (0,v): insertion of vertex v ∈ G₂

    •  (u,0): deletion of vertex u ∈ G₁

    •  (u>0,v>0): substitution of vertex u ∈ G₁ by vertex v ∈ G₂

  Optional Arguments
  ––––––––––––––––––––

    •  insert_cost::Function=v->1.0

    •  delete_cost::Function=u->1.0

    •  subst_cost::Function=(u,v)->0.5

Therefore, if you specify that the substitution cost should be zero for identical vertices, you end up with an edit distance of zero:

julia> dist, _ = edit_distance(G1, G2, subst_cost=(u, v) -> (u == v ? 0 : 1))
(0.0, Tuple[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)])

You may wonder why the edit path is still non-empty. This is a design choice specifying that we have to substitute every vertex of G1 with the corresponding vertex of G2, even if they have the same label.
Perhaps that is something we should change, or at least make more explicit in the documentation.

Does that help you?

[etiennedeg]

edit_distance is actually really weird. Generally, when computing edit_distance on graphs, we are more interested in introducing a cost for edge substitutions rather than vertex substitution. If we consider only vertex substitution, the problem is equivalent to matching the maximum number of labels (which is trivial and rather uninteresting). Why define graphs with edges if we are only interested in the set of labels of vertices?
The paper cited in the documentation references costs for edge substitution.
Actually, the code assigns a substitution for every assignment of vertices, even when the graph is unlabelled, which makes no sense. A substitution cost for vertices should only happen when vertices have distinct labels, so I would qualify the actual behavior as a bug.

[AndreudeDonato]

Thank you for the responses, I actually tried that but now the opposite problem arises, for two graphs that are non-isomorphic the distance is 0.0, which shouldn't be the case.

graph1 = ((1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (4, 6), (5, 6))
graph2 = ((1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 5), (3, 6), (4, 5), (4, 6))

julia> dist, _ = edit_distance(G1, G2, subst_cost=(u, v) -> (u == v ? 0 : 1))
julia> print(dist)

0.0

[gdalle]

Yeah, I can reproduce this but I have no clue why this happens. @etiennedeg ?

[etiennedeg]

Yes, I identified the issue, this function is totally broken. I started working on a fix, but I get caught by other occupations. I will try to get something clean this week-end.

[simonschoelly]

See also sbromberger/LightGraphs.jl#1036 and sbromberger/LightGraphs.jl#1087