Property Testing in Gaussian Graphical Models: Trees and Small Separation Numbers

• Authors: Luc P Devroye, Gábor Lugosi and Piotr Zwiernik
• Vol. 15, No. 2, May 2026

We study property testing for graphical models in a setting where an algorithm may adaptively query individual entries of the covariance matrix (Formula presented), and cost is measured by the number of queried entries. Under natural (strong) faithfulness assumptions, we design divide-and-conquer tests guided by balanced separators that operate on small submatrices and avoid global matrix inversion. Our first result is a tester for whether the underlying graph is a tree; with high probability it decides correctly using a subquadratic number of correlation queries, and for bounded maximum degree (Formula presented) the complexity is near-linear up to logarithmic factors. Our second result concerns graphs with a small separation number (hence small treewidth). We present two complementary procedures: a conditional descent test that never breaks when (Formula presented) and, upon termination, returns an (Formula presented) certificate; and a marginal descent test that, under a ‘good run’ condition, either certifies (Formula presented) or proves (Formula presented). The approach extends beyond the Gaussian case whenever reliable conditional-independence queries are available (e.g., non-paranormal models), yielding tests that access only a vanishing fraction of the entries of (Formula presented) .