Burova et al. test tree properties with sub-quadratic covariance queries
Efficient testing of tree structure in high-dimensional graphical models with minimal queries.
In a new paper on arXiv, Sofiya Burova, Francisco Calvillo, Gábor Lugosi, and Piotr Zwiernik tackle the challenge of testing properties of trees underlying high-dimensional graphical models. They adopt the covariance query model introduced by Lugosi et al. in 2021, where an algorithm can query pairwise covariances between variables. For the case where the underlying graph is a tree, the authors prove that while full reconstruction is expensive, certain global structural properties can be tested using a sub-quadratic number of queries.
The paper designs randomized tests for four fundamental properties: number of leaves, maximum degree, typical distance, and diameter. For each property, they provide explicit query complexity bounds that depend on the threshold and tolerance parameters. The results offer a practical path for verifying structural assumptions in graphical models without the overhead of full graph recovery. This work is relevant to machine learning, statistics, and theoretical computer science, with implications for model selection and validation in high-dimensional settings.
- Sub-quadratic query complexity for testing tree properties like leaves, max degree, typical distance, and diameter.
- Builds on the covariance query model (Lugosi et al., 2021) for graphical model structure testing.
- Explicit query complexity bounds depending on target threshold and tolerance parameters are provided.
Why It Matters
Enables efficient verification of tree structure in high-dimensional models, reducing computational costs in graphical model selection.