用少量协方差查询高效检测树形图的全局结构特性
Testing properties of trees in graphical models with covariance queries
- 基于协方差查询设计随机测试算法
- 仅需亚二次查询即可检验叶子数、最大度等性质
- 适用于高维图模型中快速验证树结构特征
我们研究高维图模型中底层图的性质测试问题。采用Lugosi等人（2021）提出的协方差查询模型，聚焦于树形图情形。研究表明，尽管完整重构树结构代价较高，但若干全局结构性质可高效测试。我们设计了针对叶子数、最大度、典型距离和直径等基本性质的随机测试方法，均只需亚二次数量的查询。对每类性质，给出了依赖于目标阈值与容差参数的显式查询复杂度界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。