The paper presents a learning algorithm for learning the structure of Markov Networks by   exploring the connection between Arithmetic Circuits and MNs. This allows them to employ their   previous work on learning ACs to learn a sub-set of MNs.

The main theme in the paper is to use “inference complexity as a learning bias.” Typically, in Markov network structure learning, one measures inference complexity using the number of edges added to the graph. In the present paper, the authors propose a more fine-grained measure: the number of edges added to an arithmetic circuit. As the authors show, this fine-grained measure yields an order of magnitude improvement in accuracy on several interesting benchmarks (I like the empirical evaluation).