Statistical graph space analysis. (December 2016)

• Record Type: Journal Article
• Authors: Jain, Brijnesh J.
• Is Part Of: Pattern recognition. Volume 60(2016:Dec.)
• Page Start: 802
• Page End: 812
• Publication Date: 2016-12
• Subjects: Graph edit distance -- Graph matching -- Fréchet mean -- Geometric midpoint -- Consistent estimator -- Majorize–minimize algorithm; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2016.06.023
• Languages: English
• ISSNs: 0031-3203

Abstract

Abstract: The sample mean is one of the most fundamental concepts in statistics. Properties of the sample mean that are well-defined in Euclidean spaces become unclear in graph spaces. This paper proposes conditions under which the following properties are valid: existence, uniqueness, and consistency of means, the midpoint property, necessary conditions of optimality, and convergence results of mean algorithms. The theoretical results address common misconceptions about the graph mean in graph edit distance spaces, serve as a first step towards a statistical analysis of graph spaces, and result in a theoretically well-founded mean algorithm that outperformed six other mean algorithms with respect to solution quality on different graph datasets representing images and molecules. Abstract : Highlights: A first step towards a theory of statistical graph space analysis is proposed. MMM-algorithm is proposed that outperformed six other mean algorithms. Necessary conditions of optimality are proved. Convergence of MMM-algorithm is shown. Basic statistical and geometrical properties are shown.