Markov random fields are used to model high dimensional distributions in a number of applied areas. Much recent interest has been devoted to the reconstruction of the dependency structure from independent samples from the Markov random fields. We analyze a simple algorithm for reconstructing the underlying graph defining a Markov random field on @math nodes and maximum degree @math given observations. We show that under mild non-degeneracy conditions it reconstructs the generating graph with high probability using @math samples where @math depend on the local interactions. For most local interaction @math are of order @math . Our results are optimal as a function of @math up to a multiplicative constant depending on @math and the strength of the local interactions. Our results seem to be the first results for general models that guarantee that the generating model is reconstructed. Furthermore, we provide explicit @math running time bound. In cases where the measure on the graph has correlation decay, the running time is @math for all fixed @math . We also discuss the effect of observing noisy samples and show that as long as the noise level is low, our algorithm is effective. On the other hand, we construct an example where large noise implies non-identifiability even for generic noise and interactions. Finally, we briefly show that in some simple cases, models with hidden nodes can also be recovered.
@cite_7: The problem of graphical model selection is to correctly estimate the graph structure of a Markov random field given samples from the underlying distribution. We analyze the information-theoretic limitations of this problem under high-dimensional scaling, in which the graph size p and the number of edges k (or the maximum degree d) are allowed to increase to infinity as a function of the sample size n. For pairwise binary Markov random fields, we derive both necessary and sufficient conditions on the scaling of the triplet (n, p, k) (or the triplet (n, p, d)) for asympotically reliable reocovery of the graph structure.
Subsequent to our work being posted on the Arxiv, Santhanam and Wainwright @cite_7 again considered essentially the problem for the Ising model, producing nearly matching lower and upper bounds on the asymptotic sampling complexity. Again their conditions do not apply to the low temperature regime. Another key difference from our work is that they restrict attention to the Ising model, i.e. Markov random fields with pairwise potentials and where each variable takes two values. Our results are not limited to pairwise interactions and apply to the more general setting of MRFs with potentials on larger cliques.