研究高维稀疏几何图的谱特性,实现对潜在几何结构的精确恢复。
Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs
- 通过可复用的去耦合与矩阵集中框架分析稀疏几何图的谱行为。
- 在连接尺度下,邻接矩阵与期望偏差为O(√(np log n)),优于已有结果。
- 首次在中等分离度下给出高斯混合块模型的精确恢复保证,适合图学习研究者。
我们研究由高维球面或高斯潜在向量生成的稀疏阈值随机几何图。尽管每条边的边际概率为p,共享潜在变量导致邻接项相关。在连接尺度np=Ω(log n)下,球面邻接矩阵以高概率满足‖A−EA‖op=O(√(np log n)+npτ),其中τ为帽阈值;高斯向量情形需控制径向波动,类似估计成立。该结果在更弱假设下改进了Liu等(2023)的谱界,并强化了Abdalla等(2024)对同质Kuramoto模型的全局同步保证。主特征空间能估计潜在几何结构。当np≫log n时,在球面模型中若log(1/p)≪d≪np log(1/p)/log n,或高斯模型中log²(1/p) log n≪d≪np log(1/p)/log n,向量与相对格拉姆矩阵误差消失,优于Li和Schramm(2023)的恢复条件。针对其提出的高斯混合块模型,本文设计的多项式时间半定规划首次在连接尺度下提供精确恢复保证。在更大分离度下,固定边密度会引入孤立顶点,使精确恢复不可行。所提可复用的去耦合与矩阵集中框架避免使用迹矩法,适用于具有潜在向量的广泛随机图模型。
原文摘要 · Abstract (English)
We study sparse threshold random geometric graphs generated by high-dimensional spherical or Gaussian latent vectors. Although each edge has marginal probability $p$, shared latent variables make the adjacency entries dependent. At the connectivity scale $np=Ω(\log n)$, the spherical adjacency matrix satisfies, with high probability,$\|A-\mathbb E A\|_{\mathrm{op}}=O\left(\sqrt{np\log n}+npτ\right)$, where $τ$ is the cap threshold; an analogous estimate holds for Gaussian vectors after controlling radial fluctuations. This sharpens the spectral bound in Liu, Mohanty, Schramm, and Yang (2023) under weaker assumptions and strengthens the global-synchronization guarantee of Abdalla, Bandeira, and Invernizzi (2024) for the homogeneous Kuramoto model. The leading eigenspace also estimates the latent geometry. When $np\gg\log n$, vector and relative Gram-matrix errors vanish for$\log(1/p)\ll d\ll np\log(1/p)/\log n$ in the spherical model and $\log^2(1/p)\log n\ll d\ll np\log(1/p)/\log n$ in the Gaussian model, improving the recovery conditions of Li and Schramm (2023). For the Gaussian mixture block model introduced there, a polynomial-time semidefinite program gives, to our knowledge, the first exact-recovery guarantee at the connectivity scale in a moderate-separation regime. At much larger separation, fixed edge density creates isolated vertices and makes exact recovery impossible. Our reusable decoupling and matrix concentration framework avoids trace-moment methods and applies broadly to random graph models with latent vectors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。