Learning Structure of Power-Law Markov Networks

We consider the problem of learning the underlying graph structure of discrete Markov networks based on power-law graphs, generated using the configuration model. We translate the learning problem into an equivalent channel coding problem and obtain necessary conditions for solvability in terms of problem parameters. In particular, we relate the exponent of the power-law graph to the hardness of the learning problem, and show that more number of samples are required for exact recovery of discrete power-law Markov graphs with small exponent values. We develop an efficient learning algorithm for accurate reconstruction of graph structure of Ising model on power-law graphs. Finally, we show that order-wise optimal number of samples suffice for recovering the exact graph under certain constraints on Ising model parameters and scalings of node degrees.