Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models

A Graphical Model (GM) describes a probability distribution over a set of random variables which factorizes over the edges of a graph. It is of interest to recover the structure of GMs from random samples. The graphical structure contains valuable information on the dependencies between the random variables. In fact, the neighborhood of a random variable is the minimal set that provides us maximum information about this variable. Unsurprisingly, GM reconstruction plays an important role in various fields such as the study of gene expression [1], protein interactions [2], neuroscience [3], image processing [4], sociology [5] and even grid science [6, 7]. The origin of the GM reconstruction problem is traced back to the seminal 1968 paper by Chow and Liu [8], where the problem was posed and resolved for the special case of tree-structured GMs. In this special tree case the maximum likelihood estimator is tractable and is tantamount to finding a maximum weighted spanning-tree. However, it is also known that in the case of general graphs with cycles, maximum likelihood estimators are intractable as they require computation of the partition function of the underlying GM, with notable exceptions of the Gaussian GM, see for instance [9], and some other special cases, like planar Ising models without magnetic field [10]. 1 A lot of efforts in this field has focused on learning Ising models, which are the most general GMs over binary variables with pairwise interaction/factorization. Early attempts to learn the Ising model structure efficiently were heuristic, based on various mean-field approximations, e.g.