Region Detection in Markov Random Fields: Gaussian Case

In this work we consider the problem of model selection in Gaussian Markov fields in the sample deficient scenario. The benchmark information-theoretic results in the case of d-regular graphs require the number of samples to be at least proportional to the logarithm of the number of vertices to allow consistent graph recovery. When the number of samples is less than this amount, reliable detection of all edges is impossible. In many applications, it is more important to learn the distribution of the edge (coupling) parameters over the network than the specific locations of the edges. Assuming that the entire graph can be partitioned into a number of spatial regions with similar edge parameters and reasonably regular boundaries, we develop new information-theoretic sample complexity bounds and show that even bounded number of samples can be enough to consistently recover these regions. We also introduce and analyze an efficient region growing algorithm capable of recovering the regions with high accuracy. We show that it is consistent and demonstrate its performance benefits in synthetic simulations. Markov random fields, or undirected probabilistic graphical models, provide a structured representation of the joint distributions of families of random variables. A Markov random field is an association of a set of random variables with the vertices of a graph, where the missing edges describe conditional independence properties among the variables [1]. It was shown by Hammersley and Clifford in their unpublished work [1] that the joint probability distribution specified by such a model factorizes according to the underlying graph. The practical importance of Markov random field is hard to overestimate. They have been applied to a large number of fields, including bioinformatics, social science, control theory, civil engineering, political science, epidemiology, image processing, marketing analysis, and many others. For instance, a graphical model may be used to represent friendships between people in a social network [3] or links between organisms with the propensity to spread an infectious disease [28]. This work was supported by the Fulbright Foundation and Office of Navy Research grant N00014-17-1-2075. 2 Given the graph structure, the most common computational tasks include calculating marginals, maximum a posteriori assignments, the partition function, sampling from the distribution and other questions of statistical inference. On the other hand, in many applications estimating the unknown edge structure of the underlying graph, also known as model selection or inverse problem, has attracted a great deal of attention. Naturally, both problems are essentially challenging especially in high dimensional scenarios and are known to be NPhard for general models [2, 3]. A variety of methods have been proposed to address this problem.