Graph Edit Distance

Question

Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance, Advances in Computer Vision and Pattern Recognition.

Link: https://www.springer.com/cda/content/document/cda_downloaddocument/9783319272511-c2.pdf?SGWID=0-0-45-1545097-p177820399

Below I want to ask clarification for an example in the text as it will help to understand when we say the edge is deleted and when we call it is substituted.

In the discussion of Example-8:

Deleting u₁ costs 1, Substituting u₂ by v₃ will cost 2 (node substitution cost + deletion of (u₁,u₂)), Substituting u₃ by v₂ will cost 1 (node substitution, edge substitution: (u₂,u₃) by (v₂,v₃) ) and Substituting u₄ by v₁ will cost 2 (node substitution + deletion of (u₂,u₄)). So the total cost seems to be 6 but the text mentions it as 4.

I have also added the source as an image for convenience, thanks in advance!

Answer 1

No, it is not an error.

u1 is deleted. Cost 1.
u2 is substituted with v3. Cost 0 (Equal labeling).
This Operation together with the first Node deletion implies the deletion of edge (u1, u2). Cost 1.
u3 is substituted with v2. Cost 1.
This implies the substitution of edge (u2,u3) with (v3,v2) with cost 0.
u4 is substituted with v1. Cost 0.
This implies the substitution of edge (u3,u4) with (v2,v1) with cost 0 and the deletion of edge (u1,u4) with cost 1.

Hence, we have a total cost of 4.