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

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