Abstract We study property testing for graphical models in a setting where an algorithm may adaptively query individual entries of the covariance matrix, 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 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 sn (G) k and, upon termination, returns an O (k (n/k) ) certificate; and a marginal descent test that, under a ‘good run’ condition, either certifies sn (G) 2k or proves sn (G) k. 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.
Devroye et al. (Thu,) studied this question.