判断两个加权随机图边是否相关，给出可检测的理论边界。
Testing Dependency of Weighted Random Graphs
- 将边依赖性检测建模为假设检验问题。
- 确定了在节点数和权重分布下检测的理论可行性阈值。
- 发现统计与计算之间的固有鸿沟，适合理论研究者阅读。
本文研究检测两个加权随机图之间边依赖性的任务。将该任务形式化为一个简单的假设检验问题：零假设下，两个观测图在统计上独立；备择假设下，一个图的边依赖于另一个图经均匀随机顶点置换后的版本。针对一般的边权分布，我们建立了最优检测在信息论上可行或不可行的阈值，该阈值取决于观测图的总节点数及权重生成分布。最后，我们识别出一个统计-计算间隙，并利用低阶多项式框架提供了该间隙固有的证据。
原文摘要 · Abstract (English)
In this paper, we study the task of detecting the edge dependency between two weighted random graphs. We formulate this task as a simple hypothesis testing problem, where under the null hypothesis, the two observed graphs are statistically independent, whereas under the alternative, the edges of one graph are dependent on the edges of a uniformly and randomly vertex-permuted version of the other graph. For general edge-weight distributions, we establish thresholds at which optimal testing becomes information-theoretically possible or impossible, as a function of the total number of nodes in the observed graphs and the generative distributions of the weights. Finally, we identify a statistical-computational gap, and present evidence suggesting that this gap is inherent using the framework of low-degree polynomials.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。