论文标题
测试未标记的随机图的相关性
Testing correlation of unlabeled random graphs
论文作者
论文摘要
我们研究了检测两个随机图与$ n $未标记节点之间的边缘相关性的问题。这被形式化为假设检验问题，在零假设下，这两个图是独立生成的。在替代方案下，这两个图在某些潜在节点对应关系下与边缘相关，但具有与空的边缘分布相同。对于高斯加权的完整图和密集的Erdős-rényi图（带有边缘概率$ n^{ - o（1）} $），我们确定最佳测试误差概率在$ n \ $ n \ fos \ suftty $中表现为相位过渡的尖锐阈值。对于具有边缘概率$ n^{ - ω（1）} $的稀疏Erdős-rényi图，我们确定恒定因子内的阈值。 不可能结果的证明是有条件的第二阶段方法的应用，在该方法中，我们通过仔细调节相交图的典型行为（由观测图中的边缘组成），并考虑边缘上诱导的随机置换的循环结构，通过仔细调节了可能性比的截断。值得注意的是，在稀疏的制度中，这是通过利用亚临界Erdős-rényi图的伪井结构来完成的，并仔细列举了可以从边缘置换率的短轨道组装的副孔。
We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independently generated; under the alternative, the two graphs are edge-correlated under some latent node correspondence, but have the same marginal distributions as the null. For both Gaussian-weighted complete graphs and dense Erdős-Rényi graphs (with edge probability $n^{-o(1)}$), we determine the sharp threshold at which the optimal testing error probability exhibits a phase transition from zero to one as $n\to \infty$. For sparse Erdős-Rényi graphs with edge probability $n^{-Ω(1)}$, we determine the threshold within a constant factor. The proof of the impossibility results is an application of the conditional second-moment method, where we bound the truncated second moment of the likelihood ratio by carefully conditioning on the typical behavior of the intersection graph (consisting of edges in both observed graphs) and taking into account the cycle structure of the induced random permutation on the edges. Notably, in the sparse regime, this is accomplished by leveraging the pseudoforest structure of subcritical Erdős-Rényi graphs and a careful enumeration of subpseudoforests that can be assembled from short orbits of the edge permutation.
