  In many statistical applications, the dimension is too large to handle for
standard high-dimensional machine learning procedures. This is particularly
true for graphical models, where the interpretation of a large graph is
difficult and learning its structure is often computationally impossible either
because the underlying graph is not sufficiently sparse or the number of
vertices is too large. To address this issue, we develop a procedure to test a
property of a graph underlying a graphical model that requires only a
subquadratic number of correlation queries (i.e., we require that the algorithm
only can access a tiny fraction of the covariance matrix). This provides a
conceptually simple test to determine whether the underlying graph is a tree
or, more generally, if it has a small separation number, a quantity closely
related to the treewidth of the graph. The proposed method is a
divide-and-conquer algorithm that can be applied to quite general graphical
models.
