  We consider the problem of reconstructing the graph underlying an Ising model
from i.i.d. samples. Over the last fifteen years this problem has been of
significant interest in the statistics, machine learning, and statistical
physics communities, and much of the effort has been directed towards finding
algorithms with low computational cost for various restricted classes of
models. Nevertheless, for learning Ising models on general graphs with $p$
nodes of degree at most $d$, it is not known whether or not it is possible to
improve upon the $p^{d}$ computation needed to exhaustively search over all
possible neighborhoods for each node.
  In this paper we show that a simple greedy procedure allows to learn the
structure of an Ising model on an arbitrary bounded-degree graph in time on the
order of $p^2$. We make no assumptions on the parameters except what is
necessary for identifiability of the model, and in particular the results hold
at low-temperatures as well as for highly non-uniform models. The proof rests
on a new structural property of Ising models: we show that for any node there
exists at least one neighbor with which it has a high mutual information. This
structural property may be of independent interest.
