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 u1 costs 1, Substituting u2 by v3 will cost 2 (node substitution cost + deletion of (u1,u2)), Substituting u3 by v2 will cost 1 (node substitution, edge substitution: (u2,u3) by (v2,v3) ) and Substituting u4 by v1 will cost 2 (node substitution + deletion of (u2,u4)). 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!

enter image description here


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.