  In this paper, we study the problem of inferring time-varying Markov random
fields (MRF), where the underlying graphical model is both sparse and changes
sparsely over time. Most of the existing methods for the inference of
time-varying MRFs rely on the regularized maximum likelihood estimation (MLE),
that typically suffer from weak statistical guarantees and high computational
time. Instead, we introduce a new class of constrained optimization problems
for the inference of sparsely-changing MRFs. The proposed optimization problem
is formulated based on the exact $\ell_0$ regularization, and can be solved in
near-linear time and memory. Moreover, we show that the proposed estimator
enjoys a provably small estimation error. As a special case, we derive sharp
statistical guarantees for the inference of sparsely-changing Gaussian MRFs
(GMRF) in the high-dimensional regime, showing that such problems can be
learned with as few as one sample per time. Our proposed method is extremely
efficient in practice: it can accurately estimate sparsely-changing graphical
models with more than 500 million variables in less than one hour.
