Properties of the Sample Mean in Graph Spaces and the Majorize-Minimize-Mean Algorithm
This work addresses fundamental statistical challenges for researchers and practitioners working with graph-structured data, such as in image analysis and molecular science, by providing a robust method for computing graph means.
The paper tackled the problem of defining and computing a sample mean in graph spaces, where traditional Euclidean properties fail, by presenting conditions to resolve six open problems and proposing the Majorize-Minimize-Mean (MMM) Algorithm. Experiments on image and molecule graph datasets showed that the MMM-Algorithm best approximates a sample mean compared to six other mean algorithms.
One of the most fundamental concepts in statistics is the concept of sample mean. Properties of the sample mean that are well-defined in Euclidean spaces become unwieldy or even unclear in graph spaces. Open problems related to the sample mean of graphs include: non-existence, non-uniqueness, statistical inconsistency, lack of convergence results of mean algorithms, non-existence of midpoints, and disparity to midpoints. We present conditions to resolve all six problems and propose a Majorize-Minimize-Mean (MMM) Algorithm. Experiments on graph datasets representing images and molecules show that the MMM-Algorithm best approximates a sample mean of graphs compared to six other mean algorithms.