# Learning partial correlation graphs and graphical models by covariance queries

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2019.

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

- [Learning Linear Non-Gaussian Polytree Models](https://mlsanity.com/paper/2208.06701/) (2022)
- [Hebbian learning inspired estimation of the linear regression parameters from queries](https://mlsanity.com/paper/2311.03483/) (2023)
- [Compressive Recovery of Sparse Precision Matrices](https://mlsanity.com/paper/2311.04673/) (2023)
- [Learning Multi-Frequency Partial Correlation Graphs](https://mlsanity.com/paper/2311.15756/) (2023)
- [Testing properties of trees in graphical models with covariance queries](https://mlsanity.com/paper/2605.15996/) (2026)

## Abstract (arXiv)

We study the problem of recovering the structure underlying large Gaussian graphical models or, more generally, partial correlation graphs. In high-dimensional problems it is often too costly to store the entire sample covariance matrix. We propose a new input model in which one can query single entries of the covariance matrix. We prove that it is possible to recover the support of the inverse covariance matrix with low query and computational complexity. Our algorithms work in a regime when this support is represented by tree-like graphs and, more generally, for graphs of small treewidth. Our results demonstrate that for large classes of graphs, the structure of the corresponding partial correlation graphs can be determined much faster than even computing the empirical covariance matrix.