揭示多图对齐中统计与计算能力的鸿沟，指出高效算法难以突破的瓶颈。
Statistical-computational gap in multiple Gaussian graph alignment
- 推广信息阈值理论，分析图数量随节点增长时的对齐难度变化。
- 证明当相关性ρ<1时，低阶算法无法实现非平凡估计，存在计算障碍。
- 适用于研究图对齐、统计推断与复杂结构优化的学者，尤其关注计算极限者。
我们研究了多高斯图对齐中的统计-计算鸿沟。首先将Vassaux和Massoulié（2025）建立的信息阈值推广到图数 $p$ 随节点数 $n$ 增长的情形：当 $p \leq O(n/\log n)$ 时，恢复原结果；而当 $p \geq \Omega(n/\log n)$ 时，问题难度等价于将单个图与未知“信号”图对齐。此外，当 $\log p = \omega(\log n)$ 时，部分恢复与精确恢复的信息阈值不再重合，与 $\log p=O(\log n)$ 下的全有或全无现象相异。随后，我们在低度框架下首次给出（多图）高斯图对齐的计算障碍：当相关性 $ρ < 1$ 时，忽略对数因子，低度算法无法实现非平凡估计。结果表明，多项式时间内对齐 $p$ 张图的难度，与对齐两图的难度相当，仅差对数因子。这些发现刻画了统计-计算鸿沟的存在，并为处理复杂组合双维结构提供了又一例证。
原文摘要 · Abstract (English)
We investigate the existence of a statistical-computational gap in multiple Gaussian graph alignment. We first generalize a previously established informational threshold from Vassaux and Massoulié (2025) to regimes where the number of observed graphs $p$ may also grow with the number of nodes $n$: when $p \leq O(n/\log(n))$, we recover the results from Vassaux and Massoulié (2025), and $p \geq Ω(n/\log(n))$ corresponds to a regime where the problem is as difficult as aligning one single graph with some unknown "signal" graph. Moreover, when $\log p = ω(\log n)$, the informational thresholds for partial and exact recovery no longer coincide, in contrast to the all-or-nothing phenomenon observed when $\log p=O(\log n)$. Then, we provide the first computational barrier in the low-degree framework for (multiple) Gaussian graph alignment. We prove that when the correlation $ρ$ is less than $1$, up to logarithmic terms, low degree non-trivial estimation fails. Our results suggest that the task of aligning $p$ graphs in polynomial time is as hard as the problem of aligning two graphs in polynomial time, up to logarithmic factors. These results characterize the existence of a statistical-computational gap and provide another example in which polynomial-time algorithms cannot handle complex combinatorial bi-dimensional structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。