We propose a penalized pseudo-likelihood criterion to estimate the graph of conditional dependencies in a discrete Markov random field that can be partially observed. We prove the convergence of the estimator in the case of a finite or countable infinite set of nodes. In the finite case, the underlying graph can be recovered with probability one, while in the countable infinite case, we can recover any finite sub-graph with probability one by allowing the candidate neighborhoods to grow as a function o(log n), with n the sample size. Our method requires minimal assumptions on the probability distribution, and contrary to other approaches in the literature, the usual positivity condition is not needed. We evaluate the performance of the estimator on simulated data, and we apply the methodology to a real dataset of stock index markets in different countries.