A polygraph test for trustworthy structural similarity. (March 2017)

• Record Type: Journal Article
• Authors: Naudé, Kevin A.; Greyling, Jean H.; Vogts, Dieter
• Is Part Of: Information systems. Volume 64(2017)
• Page Start: 194
• Page End: 205
• Publication Date: 2017-03
• Subjects: Similarity measures -- Distance measures -- Similarity judgment errors -- Similarity judgment quality -- Information retrieval; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2016.07.005
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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. Abstract : Highlights: 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.