A polygraph test for trustworthy structural similarity

• Published in: Information systems (Oxford) 2017-03, Vol.64, p.194-205
• Main Authors: Naudé, Kevin A., Greyling, Jean H., Vogts, Dieter
• Format: Article
• Language: English
• Subjects: Distance measures; Information retrieval; Similarity judgment errors; Similarity judgment quality; Similarity measures
• ISSN: 0306-4379; 1873-6076
• DOI: 10.1016/j.is.2016.07.005

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. •A method for the direct evaluation and characterisation of structural similarity measures is proposed.•The method is based upon the similarity of input graphs relative to a reference graph.•Ground truth data are obtained through a constructive process.•The method is demonstrated in a study comparing three similarity measures.•The similarity measure due to Blondel et al. is shown to exhibit stronger performance on larger graphs with a diverse supply of labels.