Statistical graph space analysis

•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.

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.