Graphical models are useful in modelling multivariate dependencies; learning their structure based on data is a key problem. Classical methods for learning Gaussian graphical models rely on storing the entire covariance matrix, in high-dimensional settings this is often too expensive. We investigate an algorithm of Lugosi et al. (2021) that is able to learn Gaussian graphical models, in particular partial correlation graphs, in a short time using only a few entries of the covariance matrix. We extend that algorithm to an empirical setting using the notion of hypothesis testing. We discuss choosing appropriate significance levels from two different points of view, multiple testing and testing each hypothesis at the same significance level. We prove analogous results on the correctness and time complexity of the algorithm and we show that this is possible using only a few entries of the sample covariance matrix. We usually do so by bridging the gap between the empirical and non-empirical case and combine these results with results of Lugosi et al. (2021). Finally, we extend the algorithm and the results from Gaussian to binary distributions and examine each algorithm in simulations using synthetically generated data.     «

Graphical models are useful in modelling multivariate dependencies; learning their structure based on data is a key problem. Classical methods for learning Gaussian graphical models rely on storing the entire covariance matrix, in high-dimensional settings this is often too expensive. We investigate an algorithm of Lugosi et al. (2021) that is able to learn Gaussian graphical models, in particular partial correlation graphs, in a short time using only a few entries of the covariance matrix. W...     »