I have a question about `nx.optimal_edit_paths(G1, G2)`.

[frhyme]

I have been conducting a experiment for computing graph similarity.
I have a question about nx.optimal_edit_paths(G1, G2). In the documentation of it, it is written that this function Returns all minimum-cost edit paths transforming G1 to G2.

I use the function in my code and I run it. my code is below. Even though G1 and G2 are exactly same graph and their graph_edit_cost is 0, there a a lot of optimal_edit_paths.

N = 3
G1 = nx.complete_graph(N)
G2 = nx.complete_graph(N)

edit_path, graph_edit_cost = nx.optimal_edit_paths(G1, G2)
print(f"graph edit cost: {graph_edit_cost}")
for p in edit_path:
    node_edit, edge_edit = p
    print(f"node_edit: {node_edit}")
    print(f"edge_edit: {edge_edit}")
    print("--"*30)

the output is below. As I said it before, graph_edit_cost is zero because G1 and G2 are exactly same graphs. but there are lots of optimal path when paths was derived by nx.optimal_edit_paths(G1, G2). I don't know why this happend. It doesn't look like 'optimal' because they don't have same edit cost.

graph edit cost: 0.0
node_edit: [(0, 0), (1, 1), (2, 2)]
edge_edit: [((0, 1), (0, 1)), ((0, 2), (0, 2)), ((1, 2), (1, 2))]
------------------------------------------------------------
node_edit: [(0, 0), (2, 1), (1, 2)]
edge_edit: [((0, 2), (0, 1)), ((0, 1), (0, 2)), ((1, 2), (1, 2))]
------------------------------------------------------------
node_edit: [(1, 0), (0, 1), (2, 2)]
edge_edit: [((0, 1), (0, 1)), ((0, 2), (1, 2)), ((1, 2), (0, 2))]
------------------------------------------------------------
node_edit: [(1, 0), (2, 1), (0, 2)]
edge_edit: [((1, 2), (0, 1)), ((0, 1), (0, 2)), ((0, 2), (1, 2))]
------------------------------------------------------------
node_edit: [(2, 0), (0, 1), (1, 2)]
edge_edit: [((0, 2), (0, 1)), ((0, 1), (1, 2)), ((1, 2), (0, 2))]
------------------------------------------------------------
node_edit: [(2, 0), (1, 1), (0, 2)]
edge_edit: [((1, 2), (0, 1)), ((0, 1), (1, 2)), ((0, 2), (0, 2))]
------------------------------------------------------------

And also, if the function is correct, How can I transform G1 to G2 base on that operations(node_edit, edge_edit)? I don't know how those operations have to be applied to G2 to make G2.

I always appreciate your help in this library. becasue of that, I've learned a lot about network science.

If you feel my text is rude or not polite, it is because of my lack of english. sorry about that.

[rossbar]

If you feel my text is rude or not polite, it is because of my lack of english. sorry about that.

Nothing at all to be sorry about @frhyme , thanks for the question.

I'm not familiar at all with optimal_edit_paths, but I just wanted to call your attention to #4102 - maybe the discussion will prove useful.

[dschult]

This question is quite old, and I think a complete answer requires looking at the reference paper to see how they count the number of edits and in particular how they check for isomorphism with G2 after the edits. But here's a partial answer:

The edit paths you report all have 3 node edits and 3 edge edits. That means the length of those two lists is 6 total for all of the edit paths. They are equivalent despite the first being the "identity path"(? a term I just made up).

But, as you point out, the two graphs are isomorphic, so the edit distance should be 0 if distance is the number of changes needed to make G1 isomorphic to G2.

I suspect the algorithm actually computes the number of changes needed to convert G1 to G2. Said another way, it doesn't count the 6 edits as part of the edit cost. In fact if you look closely, these 6 paths consist precisely of the isomorphism mappings from G1 to G2. They are simply renaming the nodes and edges and thus have no cost.

This question shows that the documentation needs more information about what is returned here (i.e. what is an edit path?). That should be sufficient to close this Question.

[rossbar]

It sounds like the documentation should be improved along the lines discussed above in order to close this one.