  Learning the undirected graph structure of a Markov network from data is a
problem that has received a lot of attention during the last few decades. As a
result of the general applicability of the model class, a myriad of methods
have been developed in parallel in several research fields. Recently, as the
size of the considered systems has increased, the focus of new methods has been
shifted towards the high-dimensional domain. In particular, introduction of the
pseudo-likelihood function has pushed the limits of score-based methods which
were originally based on the likelihood function. At the same time, methods
based on simple pairwise tests have been developed to meet the challenges
arising from increasingly large data sets in computational biology. Apart from
being applicable to high-dimensional problems, methods based on the
pseudo-likelihood and pairwise tests are fundamentally very different. To
compare the accuracy of the different types of methods, an extensive numerical
study is performed on data generated by binary pairwise Markov networks. A
parallelizable Gibbs sampler, based on restricted Boltzmann machines, is
proposed as a tool to efficiently sample from sparse high-dimensional networks.
The results of the study show that pairwise methods can be more accurate than
pseudo-likelihood methods in settings often encountered in high-dimensional
structure learning applications.
