# Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees

arXiv: https://arxiv.org/abs/2102.03585 · HTML: https://mlsanity.com/paper/2102.03585/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 6 Feb 2021.

## Builds on (most cited first, 7 of 7)

- [Network Inference via the Time-Varying Graphical Lasso](https://mlsanity.com/paper/1703.01958/) (2017)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions](https://mlsanity.com/paper/1708.09479/) (2017)
- [Time-dependent spatially varying graphical models, with application to brain fMRI data analysis](https://mlsanity.com/paper/1711.03701/) (2017)
- [Two Sample Inference for Populations of Graphical Models with Applications to Functional Connectivity](https://mlsanity.com/paper/1502.03853/) (2015)
- [Learning Sparse Structural Changes in High-dimensional Markov Networks: A Review on Methodologies and Theories](https://mlsanity.com/paper/1701.01582/) (2017)
- [Fast and Scalable Learning of Sparse Changes in High-Dimensional Gaussian Graphical Model Structure](https://mlsanity.com/paper/1710.11223/) (2017)

## Built on by (most cited first, 2 of 2)

- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [Efficient Inference of Spatially-varying Gaussian Markov Random Fields with Applications in Gene Regulatory Networks](https://mlsanity.com/paper/2206.10174/) (2022)

## Abstract (arXiv)

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 ℓ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.