Testing properties of trees in graphical models with covariance queries
Provides first efficient testing algorithms for structural properties of tree graphical models, addressing a gap between costly full reconstruction and practical testing needs.
The paper develops efficient randomized tests for global structural properties of trees underlying graphical models using covariance queries, achieving sub-quadratic query complexity for properties like number of leaves, maximum degree, typical distance, and diameter.
We consider the problem of testing properties of graphs underlying high-dimensional graphical models. We adopt the model of covariance queries introduced by Lugosi, Truszkowski, Velona, and Zwiernik (2021). We study the case when the underlying graph is a tree. The main results of the paper show that, while reconstructing the entire tree may be costly, certain global structural properties can be tested efficiently. In particular, we design randomized tests for global structural properties that use a sub-quadratic number of queries. We develop testing procedures for several fundamental properties, including the number of leaves, the maximum degree, the typical distance, and the diameter of the tree. For each property, we obtain explicit query complexity bounds that depend on the target threshold and tolerance parameters.