A polygraph test for trustworthy structural similarity

Do similarity or distance measures ever go wrong? The inherent subjectivity in similarity discernment has long supported the view that all judgements of similarity are equally valid, and that any selected similarity measure may only be considered more effective in some chosen domain. This article presents evidence that such a view is incorrect for the specific case of relative structural similarity. In this context, similarity and distance measures occasionally do go wrong, producing judgements that can be considered as errors in judgement. This claim is supported by a novel method for assessing the quality of structural similarity and distance functions, which is based on relative scale of similarity with respect to chosen reference objects. The method may be applied either with synthetic graph datasets or with graphs representing objects in an application domain of interest. This work demonstrates the method over synthetic datasets with common measures of structural similarity in graphs. Finally, the article identifies three distinct kinds of relative similarity judgement errors, and shows how the distribution of these errors is related to graph properties under common similarity measures.