跳转至

Graph Alignment via Birkhoff Relaxation

会议: NeurIPS 2025
arXiv: 2503.05323
代码: smv30/convex_rel_for_graph_alignment
领域: 图算法 / 组合优化
关键词: graph alignment, quadratic assignment, Birkhoff polytope, convex relaxation, phase transition, Gaussian Wigner Model

一句话总结

首次为 Birkhoff 松弛（QAP 的紧凸松弛）在高斯 Wigner 模型下建立理论保证：当噪声 \(\sigma = o(n^{-1})\) 时松弛解近似真实排列，\(\sigma = \Omega(n^{-0.5})\) 时松弛解远离真实排列，揭示了相变现象。

Problem

图对齐问题 (Graph Alignment)：给定两个 \(n\) 个顶点的无向图 \(G_1, G_2\)，要找到一个顶点映射使得边重叠最大化。数学上等价于 Quadratic Assignment Problem (QAP)：

\[\Pi^\star = \arg\min_{X \in \mathcal{P}_n} \|AX - XB\|_F^2\]

其中 \(\mathcal{P}_n\) 是 \(n \times n\) 排列矩阵集合。QAP 在最坏情况下是 NP-hard 的，甚至近似求解也很困难。

现有方法的不足：

  • GRAMPA (Fan et al.)：在 \(\sigma = O(1/\log n)\) 时成功，但需要调参正则化参数 \(\eta\)，且实际性能弱于 Birkhoff 松弛
  • Simplex 松弛 (Araya & Tyagi)：仅在 \(\sigma = 0\)（无噪声）时有理论保证
  • EIG1 (谱方法)：阈值为 \(\sigma = \Theta(n^{-7/6})\)，条件更严格
  • Birkhoff 松弛在实践中表现最优，但此前缺乏任何理论保证

Core Idea

将 QAP 的可行域从排列矩阵集 \(\mathcal{P}_n\) 松弛为其凸包——Birkhoff 多面体 \(\mathcal{B}_n\)（即所有双随机矩阵的集合），得到 Birkhoff 松弛：

\[X^\star = \arg\min_{X \in \mathcal{B}_n} \|AX - XB\|_F^2\]

这是 QAP 的最紧凸松弛（tight convex relaxation）。核心贡献是证明了松弛解 \(X^\star\) 与真实排列 \(\Pi^\star\) 之间的距离存在相变 (phase transition)：

噪声条件 行为
\(\sigma = o(n^{-1})\) \(\|X^\star - \Pi^\star\|_F^2 = o(n)\)，小扰动
\(\sigma = \Omega(n^{-0.5})\) \(\|X^\star - \Pi^\star\|_F^2 = \Omega(n)\)，远离

Method

Gaussian Wigner Model 设定

输入图的（加权）邻接矩阵来自相关的 Gaussian Orthogonal Ensemble (GOE)：

  • \(A\) 是 GOE 矩阵：\(A_{ii} \sim N(0, 2/n)\)，\(A_{ij} = A_{ji} \sim N(0, 1/n)\)
  • \(B_{\pi^\star(i), \pi^\star(j)} = A_{ij} + \sigma Z_{ij}\)，其中 \(Z\) 是独立的 GOE 矩阵
  • 相关系数为 \(1/\sqrt{1 + \sigma^2}\)，\(\sigma\) 控制噪声强度

Part I: Well-Separation 证明 (\(\sigma = \Omega(n^{-0.5+\epsilon})\))

证明思路是建立 \(\|AX^\star - X^\star B\|_F^2\) 的上下界：

  1. 上界：用 \(J/n\)（均匀矩阵）作为可行解，得到 \(\|AX^\star - X^\star B\|_F^2 \leq 9n^\epsilon\)
  2. 下界：展开 \(\|AX^\star - X^\star B\|_F^2\)，利用 \(B = A + \sigma Z\) 得到关于 \(\|I - X^\star\|_F\) 的下界： $\(\|AX^\star - X^\star B\|_F^2 \geq \frac{\sigma^2 n}{4} - 2c\sigma^2 \sqrt{n} \|I - X^\star\|_F\)$
  3. 合并：两个界结合推出 \(\|I - X^\star\|_F \geq \sqrt{n}/(16c)\)

关键技术点：利用 GOE 矩阵的 \(\|Z\|_F^2 \geq n/2\) 的集中性，以及 \(\max_{i \neq j} |(AZ - ZA)_{ij}| \leq 8n^{\epsilon/2 - 0.5}\) 的对角元素界。

Part II: Small-Perturbation 证明 (\(\sigma = o(n^{-1-\epsilon})\))

这是论文最具技术性的部分，基于对偶构造 (dual certificate)：

  1. 简化版本：先考虑 \(\sigma = 0\) 的情况，此时 \(X = I\) 是最优解且 \(AX - XA = 0\)
  2. 对偶问题：引入对偶变量 \((R, \mu, \tilde{\mu}, M)\)，构造近似可行对偶解
  3. 关键构造：
    • 设 \(R = J - I\)（对角为 \(-1\)，非对角为 \(1\)）
    • 利用 GOE 矩阵的特征向量 \(\{u_i\}\) 构造 \(M = \sum_{i \neq j} \frac{\tilde{w}_{ij}}{\lambda_i - \lambda_j} u_i u_j^T\)
    • \(\mu\) 也基于特征向量构造，确保 \(\langle \mu, \mathbf{1} \rangle = 0\)（强对偶性）
  4. 核心不等式 (Lemma 6)：对任意 \(X \in \mathcal{B}_n\)： $\(\sum_{j \neq i} X_{ij} \leq 2n^{3/2 + 7\epsilon/8} \|AX - XA\|_F + 4n^{1 - \epsilon/32}\)$
  5. 辅助界 (Lemma 7)：\(\|AX^\star - X^\star A\|_F \leq c\sigma\sqrt{n}\)
  6. 合并：当 \(\sigma = n^{-1-\epsilon}\) 时得到 \(\sum_{i \neq j} X_{ij}^\star \leq 5n^{1-\epsilon/32}\)，进而 \(\|X^\star - I\|_F^2 \leq 10n^{1-\epsilon/32}\)

特征值间距的精细分析

证明中需要控制 \(\sum_{i \neq j} \frac{1}{(|\lambda_i - \lambda_j| + n^{-1-\epsilon})^2}\)。直接界给出 \(n^{4+2\epsilon}\)（太松），论文通过分离 \(|i-j|\) 大小两种情况，结合 Nguyen-Vu 的特征值间距尾界和 Markov 不等式，得到更紧的 \(n^{3+3\epsilon/2}\) 上界。引入 \(n^{-1-\epsilon}\) 正则化项是确保期望有限的关键技巧。

Rounding 过程

  • 简单 rounding：\(\hat{\pi}(i) = \arg\max_j X_{ij}^\star\)，可恢复 \(1 - o(1)\) 比例的正确对齐 (Corollary 2)
  • Hungarian projection：\(\tilde{\Pi} = \arg\max_{\Pi \in \mathcal{P}_n} \langle X^\star, \Pi \rangle\)，同样成功 (Corollary 3)

Training/Inference

本文是纯理论工作，无训练过程。实际求解 Birkhoff 松弛使用：

  • 凸优化求解器：cvxpy + SCS (Splitting Conic Solver)，use_indirect=True 以适应大规模实例
  • 后处理：Hungarian 算法将双随机矩阵投影到排列矩阵
  • 复杂度：Birkhoff 松弛是凸二次规划，可在多项式时间内求解；但实际中 \(n\) 较大时（\(n > 500\)）计算代价较高

Experiments

实验设置

  • 模型：Gaussian Wigner Model
  • 图大小：\(n = 400\)（默认），\(n \in \{100, 200, 300, 400, 500\}\)（规模实验）
  • 噪声范围：\(\sigma \in \{0, 0.1, 0.2, \ldots, 1.0\}\)
  • 对比方法：GRAMPA（\(\eta = 0.2\)）、Simplex 松弛、Birkhoff 松弛
  • 重复次数：每组参数 10 次取平均
  • 硬件：CPU + 50GB 内存，每实例最大运行时间 3 小时

Results

三种松弛方法对比 (\(n = 400\))

方法 100% 对齐的最大 \(\sigma\) 性能退化起始 \(\sigma\)
Birkhoff 0.5 0.6
Simplex 0.3 0.4
GRAMPA 0.1 0.2

Birkhoff 松弛在所有噪声水平上显著优于其他两种方法。

相变行为验证

  • 当 \(\sigma \in [0.3, 0.5]\) 时，虽然 \(\|X^\star - \Pi^\star\|_F / \sqrt{n}\) 已接近 1（松弛解远离真排列），但 Hungarian rounding 后仍能完美对齐
  • 这说明 \(X^\star\) 虽然整体不接近 \(\Pi^\star\)，但仍有向 \(\Pi^\star\) 的微弱偏好，足以支撑 rounding

相变阈值的经验估计

  • 对 \(n \in \{100, \ldots, 500\}\) 做 log-log 回归，\(\|X^\star - \Pi^\star\|_F / \sqrt{n} = 0.5\) 的相变点斜率为 \(-0.45\)
  • 与理论预测的 \(\sigma = \Theta(n^{-0.5})\) 吻合（Theorem 1）

不同 \(n\) 的性能

随 \(n\) 增大，对齐成功率随 \(\sigma\) 的衰减加速，但仍然是渐进的，暗示 Birkhoff + rounding 可能在几乎常数的 \(\sigma\) 下成功。

Limitations

  1. 理论与实践的 gap：理论保证 small-perturbation 需要 \(\sigma = o(n^{-1})\)，但实验中 \(\sigma\) 可达 \(O(1)\)；population 版本的相变在 \(n^{-0.5}\)，理论仍有 \(n^{-0.5}\) 到 \(n^{-1}\) 的缺口
  2. 模型限制：仅分析 Gaussian Wigner Model（连续权重），未涉及实际更常见的 Erdős-Rényi 图（二值边）
  3. 特征向量集中性：Small-perturbation 证明强依赖 GOE 特征向量在球面上均匀分布的性质，扩展到一般 Wigner 矩阵是瓶颈
  4. Well-separation 非失败条件：\(\|X^\star - \Pi^\star\|_F = \Omega(\sqrt{n})\) 不意味着 rounding 失败，论文未能刻画 rounding 的精确阈值
  5. 计算可扩展性：SCS 求解 \(n > 500\) 的实例耗时超过 3 小时，大规模场景下不实际
  6. 无实际数据验证：仅合成数据，未在社交网络去匿名化、蛋白质对齐等实际场景中测试

My Notes

  • 理论贡献扎实：首次为 Birkhoff 松弛提供非平凡的理论保证（此前只有 \(\sigma = 0\) 的结果），对偶证书的构造技巧精妙
  • 对偶构造的直觉：设 \(R = J - I\) 意味着"惩罚所有非对角元素"，然后通过 \(M\) 和 \(\mu\) 补偿近似可行性残差。这种构造思路可能迁移到其他组合优化的凸松弛分析中
  • 相变现象的 population 版本很优雅：\(\bar{X}^\star = \epsilon I + \frac{1-\epsilon}{n}J\)，其中 \(\epsilon = \frac{2}{2 + \sigma^2(n+1)}\)，直接给出 \(\sigma \sqrt{n}\) 处的相变
  • 实验中 rounding 的"救赎效应"值得深入：\(X^\star\) 虽然 \(\|X^\star - \Pi^\star\|_F\) 大，但 Hungarian 投影仍能成功。这暗示分析 rounding 后的性能（而非松弛解本身）可能给出更优的阈值
  • 实际价值：对于 ML 中的图匹配应用（如 GNN 的 graph matching layer），Birkhoff 松弛是标准组件，本文的理论分析有助于理解其鲁棒性边界
  • 扩展方向：(1) 填补 \(n^{-1}\) 到 \(n^{-0.5}\) 的 gap；(2) 分析 rounding 后的精确阈值；(3) 推广到 Erdős-Rényi 模型

评分

  • 新颖性: ⭐⭐⭐⭐ 首个 Birkhoff 松弛在噪声模型下的相变分析，对偶证书构造方法新颖
  • 实验充分度: ⭐⭐⭐ 理论+合成实验互相印证，但缺乏真实数据验证
  • 写作质量: ⭐⭐⭐⭐ 数学严谨，结构清晰，直觉解释充分
  • 价值: ⭐⭐⭐⭐ 图匹配/QAP 凸松弛理论的重要进展，可能启发后续更优阈值的分析

相关论文