Testing properties of trees in graphical models with covariance queries
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914569356574720 |
|---|---|
| author | Burova, Sofiya Calvillo, Francisco Lugosi, Gábor Zwiernik, Piotr |
| author_facet | Burova, Sofiya Calvillo, Francisco Lugosi, Gábor Zwiernik, Piotr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15996 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Testing properties of trees in graphical models with covariance queries Burova, Sofiya Calvillo, Francisco Lugosi, Gábor Zwiernik, Piotr Machine Learning Statistics Theory 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. |
| title | Testing properties of trees in graphical models with covariance queries |
| topic | Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2605.15996 |