Testing for high‐dimensional geometry in random graphs
Testing for high‐dimensional geometry in random graphs
复制标题
随机图中的高维几何测试
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Miklós Z. Rácz
中科院分区：
文献类型：
--
作者：
Sébastien Bubeck;Jian Ding;Ronen Eldan;Miklós Z. Rácz
我们研究检测随机图中是否存在潜在高维几何结构的问题。在零假设下，观察到的图是 Erdős-Rényi 随机图 G(n, p) 的实现。在另一种情况下，图是从 G(n,p,d) 模型生成的，其中每个顶点对应于均匀分布在球体 Sd−1 上的潜在独立随机向量，并且如果对应的潜在向量足够接近，则两个顶点被连接。在密集状态下（即 p 是常数），我们提出了一种基于新量（我们称之为有符号三角形）的近乎最优且计算高效的测试程序。检测下限的证明基于 Wishart 矩阵和适当归一化的 GOE 矩阵之间总变异距离的新界限。在稀疏状态下，我们对最佳检测边界做出猜想。我们通过一些关于估计 G(n,p,d) 维数问题的初步步骤来结束本文。 © 2016 Wiley periodicals, Inc. 随机结构。阿尔格., 49, 503–532, 2016
We study the problem of detecting the presence of an underlying high‐dimensional geometric structure in a random graph. Under the null hypothesis, the observed graph is a realization of an Erdős‐Rényi random graph G(n, p). Under the alternative, the graph is generated from the G(n,p,d) model, where each vertex corresponds to a latent independent random vector uniformly distributed on the sphere Sd−1 , and two vertices are connected if the corresponding latent vectors are close enough. In the dense regime (i.e., p is a constant), we propose a near‐optimal and computationally efficient testing procedure based on a new quantity which we call signed triangles. The proof of the detection lower bound is based on a new bound on the total variation distance between a Wishart matrix and an appropriately normalized GOE matrix. In the sparse regime, we make a conjecture for the optimal detection boundary. We conclude the paper with some preliminary steps on the problem of estimating the dimension in G(n,p,d) . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 503–532, 2016