# Robust Model Selection of Gaussian Graphical Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 60 references that are in the map.
- First posted on arXiv 10 Nov 2022.

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

- [Loopy Belief Propagation for Approximate Inference: An Empirical Study](https://mlsanity.com/paper/1301.6725/) (2013)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator](https://mlsanity.com/paper/1805.07194/) (2018)
- [Robust estimation of tree structured Gaussian Graphical Model](https://mlsanity.com/paper/1901.08770/) (2019)
- [Robust Estimation of Tree Structured Ising Models](https://mlsanity.com/paper/2006.05601/) (2020)
- [Robust high-dimensional precision matrix estimation](https://mlsanity.com/paper/1501.01219/) (2015)
- [Graphical Models in Meshed Distribution Grids: Topology estimation, change detection and limitations](https://mlsanity.com/paper/1905.06550/) (2019)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Robust Gaussian Graphical Modeling with the Trimmed Graphical Lasso](https://mlsanity.com/paper/1510.08512/) (2015)
- [Robust estimation of tree structured models](https://mlsanity.com/paper/2102.05472/) (2021)
- [Robustifying Algorithms of Learning Latent Trees with Vector Variables](https://mlsanity.com/paper/2106.00885/) (2021)
- [Data Requirement for Phylogenetic Inference from Multiple Loci: A New Distance Method](https://mlsanity.com/paper/1404.7055/) (2014)
- [One Breaker is Enough: Hidden Topology Attacks on Power Grids](https://mlsanity.com/paper/1506.04303/) (2015)
- [Graphical Model Inference with Erosely Measured Data](https://mlsanity.com/paper/2210.11625/) (2022)

## Abstract (arXiv)

In Gaussian graphical model selection, noise-corrupted samples present significant challenges. It is known that even minimal amounts of noise can obscure the underlying structure, leading to fundamental identifiability issues. A recent line of work addressing this "robust model selection" problem narrows its focus to tree-structured graphical models. Even within this specific class of models, exact structure recovery is shown to be impossible. However, several algorithms have been developed that are known to provably recover the underlying tree-structure up to an (unavoidable) equivalence class. In this paper, we extend these results beyond tree-structured graphs. We first characterize the equivalence class up to which general graphs can be recovered in the presence of noise. Despite the inherent ambiguity (which we prove is unavoidable), the structure that can be recovered reveals local clustering information and global connectivity patterns in the underlying model. Such information is useful in a range of real-world problems, including power grids, social networks, protein-protein interactions, and neural structures. We then propose an algorithm which provably recovers the underlying graph up to the identified ambiguity. We further provide finite sample guarantees in the high-dimensional regime for our algorithm and validate our results through numerical simulations.