Scale-space module detection for random fields observed on a graph non embedded in a metric space

Overview & Synopsis

In the spirit of Lindeberg’s approach for image analysis on regular lattice, we adapt from a statistical viewpoint, the blob detection procedure for graphs non embedded in a metric space. We treat data observed on such a graph in the goal of detecting salient modules. This task consists in seeking subgraphs whose activity is strong or weak compared to those of their neighbors. This is performed by analyzing nodes activity at multi-scale levels. To do that, data are seen as the occurrence of a univariate random field, for which we propose a multi-scale graphical modeling. In the framework of diffusion processes, the covariance matrix of the random field is decomposed into a weighted sum of graph Laplacians at different scales. Under the assumption of Gaussian law, the maximum likelihood estimation of the weights is performed that provides a set of relevant scales. As a result, we obtain a multi-scale decomposition of the random field on which the module detection is based. This method is experimentally analyzed on simulated data and biological networks.