Learning partial correlation graphs and graphical models by covariance queries
This work addresses the computational bottleneck in structure learning for high-dimensional graphical models, offering a more efficient method for statisticians and data scientists dealing with large datasets, though it is incremental as it builds on existing graph recovery techniques.
The paper tackles the problem of efficiently recovering the structure of large Gaussian graphical models or partial correlation graphs in high-dimensional settings where storing the full covariance matrix is costly, by proposing a new input model that allows querying single covariance entries and proving that the support of the inverse covariance matrix can be recovered with low query and computational complexity for tree-like graphs and graphs of small treewidth.
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.