Validation of non-rigid registration methods is still a challenging task. Different evaluation criteria were published, yet no widely accepted gold standard exists. The aim of this paper is to provide quantitative evaluation metrics suited for clinical 3D images containing vessel trees, such as liver or brain data. We present a method to identify corresponding points on different vessel trees by extracting consistent graph minors interactively. Four different metrics based on these correspondencies are proposed.