通过伯克霍夫松弛实现图对齐，理论证明在噪声较小时可准确匹配顶点。
Graph Alignment via Birkhoff Relaxation
- 采用伯克霍夫松弛法求解图对齐问题，将复杂问题转为凸优化。
- 当噪声水平σ < n^{-1.25}时，99%以上顶点能被正确对齐。
- 适用于小噪声场景的图匹配，尤其适合高精度对齐需求的研究者。
我们研究图对齐问题，目标是找到两图间最大化边重叠的顶点对应关系。该问题属于二次分配问题（QAP），在最坏情况下即使近似求解也属于NP难。本文分析了伯克霍夫松弛这一紧致凸松弛方法，并在输入服从高斯威格纳模型时给出理论保证。具体地，加权邻接矩阵为相关高斯正交系综，相关系数为 $1/ig(\sqrt{1+\sigma^2}\big)$。设QAP最优解为 $Π^\star$，伯克霍夫松弛最优解为 $X^\star$。我们证明当 $σ = o(n^{-1.25})$ 时，$\|X^\star - Π^\star\|_F^2 = o(n)$；而当 $σ = \Omega(n^{-0.5})$ 时，$\|X^\star - Π^\star\|_F^2 = \Omega(n)$。这表明当σ较小时，$X^\star$ 是 $Π^\star$ 的微小扰动，随σ增大逐渐分离。由此可保证对 $X^\star$ 进行简单取整即可使正确对齐顶点比例达到 $1 - o(1)$，且该条件为当前最优。
原文摘要 · Abstract (English)
We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is an instance of the quadratic assignment problem (QAP), known to be NP-hard in the worst case even to approximately solve. In this paper, we analyze Birkhoff relaxation, a tight convex relaxation of QAP, and present theoretical guarantees on its performance when the inputs follow the Gaussian Wigner Model. More specifically, the weighted adjacency matrices are correlated Gaussian Orthogonal Ensemble with correlation $1/\sqrt{1+σ^2}$. Denote the optimal solutions of the QAP and Birkhoff relaxation by $Π^\star$ and $X^\star$ respectively. We show that $\|X^\star-Π^\star\|_F^2 = o(n)$ when $σ= o(n^{-1.25})$ and $\|X^\star-Π^\star\|_F^2 = Ω(n)$ when $σ= Ω(n^{-0.5})$. Thus, the optimal solution $X^\star$ transitions from a small perturbation of $Π^\star$ for small $σ$ to being well separated from $Π^\star$ as $σ$ becomes larger than $n^{-0.5}$. This result allows us to guarantee that simple rounding procedures on $X^\star$ align $1-o(1)$ fraction of vertices correctly whenever $σ= o(n^{-1.25})$. This condition on $σ$ to ensure the success of the Birkhoff relaxation is state-of-the-art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。