Testing properties of trees in graphical models with covariance queries
Authors: Sofiya Burova, Francisco Calvillo, G'abor Lugosi et al.
Summary
arXiv:2605. 15996v1 Announce Type: new Abstract: We consider the problem of testing properties of graphs underlying high-dimensional graphical models.
Relevance
Read next because Testing properties of trees in graphical models with covariance queries overlaps with clean result "Language-mismatch LoRA SFT on Qwen2.5-7B leaks the trained completion language into bystander directives the model was never trained on, absent under same-language SFT (LOW confidence)", experiment "Test FR↔IT bystander-spill symmetry at multi-seed + 5 phrasings — pooled-rate vs per-phrasing asymmetry from #239 fact-check", experiment "Language-mismatch LoRA SFT on Qwen2.5-7B leaks the trained completion language into bystander directives the model was never trained on, absent under same-language SFT (LOW confidence)". Matching terms: under, test, model. Source: arxiv stat.ML (Machine Learning).
Abstract
arXiv:2605.15996v1 Announce Type: new Abstract: 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.