多图对齐的可行性：一种贝叶斯方法

《Advances in Applied Probability》：The feasibility of multi-graph alignment: A Bayesian approach

　　

研究人员建立了两个模型中随机多图对齐可行性的阈值。在高斯模型（Gaussian model）中，研究人员展示了一个“全有或全无”现象：在临界阈值以上，精确对齐可以以高概率实现，而在阈值以下，即使部分对齐在统计上也是不可能的。在稀疏埃尔德什-雷尼模型（Erd?s–Rényi model）中，研究人员严格确定了一个阈值，低于该阈值无法实现有意义的部分对齐，并推测高于该阈值可以实现部分对齐。为了证明这些结果，研究人员在度量空间上开发了一个通用的贝叶斯估计（Bayesian estimation）框架，该框架为更广泛的高维统计问题提供了见解。

多图对齐的可行性研究——贝叶斯方法视角下的阈值分析

**研究背景**
图对齐问题（graph alignment problem）旨在从多个未标记的图中恢复节点间的对应关系，广泛应用于去匿名化、自然语言处理和蛋白质相互作用网络分析等领域。以往研究主要集中于两个图的情况，并已深入理解其信息论极限。然而，当图的数量超过两个时（即多图对齐），问题复杂度显著增加，相关研究较为有限。本文旨在研究多图对齐的可行性阈值，即从信息论角度判断在何种条件下能够从观测到的多个随机图中恢复出正确的节点排列（permutation）。研究人员在两种经典模型下展开研究：高斯模型（Gaussian model）和稀疏埃尔德什-雷尼模型（Erd?s–Rényi model）。该论文发表在《Advances in Applied Probability》上。

**主要结论**
- 在高斯模型中，存在一个临界阈值ρ₀ = √(8 log n / (p n))，其中p为图的数量，n为节点数。当相关性ρ ≥ (1+ε)ρ₀时，精确对齐（exact alignment）可以高概率实现；当ρ ≤ (1-ε)ρ₀时，即使部分对齐（partial alignment）也在统计上不可能。这一现象被称为“全有或全无”（all-or-nothing）。
- 在埃尔德什-雷尼模型中，当参数λs(1 - (1-s)^p-1) < 1时，部分对齐不可行；研究人员推测当该参数大于1时，部分对齐可行。

**主要技术方法**
研究人员开发了一个通用的贝叶斯估计框架，在度量空间上定义，适用于一类高维统计问题。具体到图对齐，将问题表述为贝叶斯推断，利用后验分布（posterior distribution）的Gibbs形式。在高斯模型中，通过计算退火自由能（annealed free energy）和淬火自由能（quenched free energy），并借助高斯二次型尾界（Hanson–Wright不等式）和浓度不等式（高斯浓度定理），证明阈值的存在。在埃尔德什-雷尼模型中，通过组合方法分析后验分布的对称性，构造大量自同构（automorphism），证明当交集图是次临界时后验质量无法集中，从而部分对齐不可行。此外，还用到最大生成树权重的新下界（定理6）。

**研究结果**
- **高斯模型（Section 3）**：通过定理1，给出了精确对齐的阈值，并展示了“全有或全无”现象。具体研究包括：3.1节将后验分布表示为Gibbs测度，哈密顿量（Hamiltonian）由边权重的高斯变量构成；3.2节通过组合计数（定理3）控制排列间的重叠度；3.3节计算退火自由能（命题6），得到上界；3.4节利用淬火自由能（命题7）和浓度性质（引理3），证明当η>0时后验质量集中在真实排列附近，当η<0时后验质量分散。
- **埃尔德什-雷尼模型（Section 4）**：通过定理2，给出部分对齐不可行的充分条件。具体研究包括：4.1节描述系统的后验分布形式（命题8），哈密顿量等于合并图的边数；4.2节利用自同构对称性（命题9），证明若σ是Γ⁽¹⁾ ∩ U⁽¹⁾(π)的自同构，则复合排列的哈密顿量不增；4.3节构造大量自同构（命题10），证明当交集图次临界时，存在大量自同构；4.4节应用引理1，证明部分估计不可行。
- **贝叶斯估计框架（Section 2）**：2.1节将图对齐问题视为贝叶斯推断；2.2节定义度量估计问题，给出部分估计和几乎精确估计的可行性判据（推论1）；2.4节提出引理1，通过构造函数F将后验质量扩散，从而证明部分估计不可行。

**讨论与结论**
研究人员对比了与并发工作（Ameen和Hajek，2023）的关系，指出高斯模型下检测阈值可能也是ρ₀。对于埃尔德什-雷尼模型，阈值与交集图H⁽¹⁾ = G⁽¹⁾ ∩ (G⁽²⁾ ∪ ... ∪ G^(p))的巨分量出现阈值一致，类似双图情况。此外，证明中用到的新结果（定理6）关于最大生成树权重的下界，可能具有独立意义。研究结论部分可翻译为：研究人员建立了多图对齐在两种模型下的可行性阈值，提供了信息论极限，并开发了适用于更广泛问题的贝叶斯估计框架。