提出一种抗干扰的图匹配算法，可在稠密图中高效恢复顶点对应关系。
Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm
- 设计带时间依赖乘法的近似消息传递迭代算法，增强特征并消除相关性。
- 在相关系数ρ为常数、扰动范围ε= o(1/(log n)^20)时，多项式时间内成功匹配。
- 首次实现对n^{1−o(1)}规模恶意扰动的鲁棒性，适合高可靠性图匹配场景。
本文研究一对具有潜在顶点对应关系的关联高斯威格纳矩阵之间的匹配恢复问题。我们关注一种鲁棒版本：观测数据为扰动输入 (A+E, B+F)，其中 (A,B) 是一对相关高斯威格纳矩阵，E,F 是分别支持在未知 εn × εn 主子块上的对抗性矩阵。我们提出一种近似消息传递（AMP）型迭代算法，在相关系数 ρ 为非消失常数且 ε = o(1/(log n)^20) 的条件下，可在多项式时间内成功恢复匹配。其关键创新在于迭代中引入随时间变化的矩阵乘法步骤，同时提升特征维度并抵消相关性。主要方法基于 extcite{DL22+, DL23+} 提出的迭代随机图匹配算法与 extcite{IS24+} 的谱预处理技术。据我们所知，该算法是首个在任意大小为 n^{1−o(1)} 的对抗扰动下仍有效的高效随机图匹配算法。
原文摘要 · Abstract (English)
In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. We are particularly interested in a robust version of this problem such that our observation is a perturbed input $(A+E,B+F)$ where $(A,B)$ is a pair of correlated Gaussian Wigner matrices and $E,F$ are adversarially chosen matrices supported on an unknown $εn * εn$ principal minor of $A,B$, respectively. We propose an approximate message passing (AMP) type iterative algorithm that succeeds in polynomial time as long as the correlation $ρ$ between $(A,B)$ is a non-vanishing constant and $ε= o\big( \tfrac{1}{(\log n)^{20}} \big)$. A key distinction from standard AMP is the introduction of a time-dependent matrix multiplication step within the iteration, which simultaneously enlarges the feature dimension and cancels the correlation during the iteration. The main methodological inputs for our result are the iterative random graph matching algorithm proposed in \cite{DL22+, DL23+} and the spectral preprocessing procedure proposed in \cite{IS24+}. To the best of our knowledge, our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n^{1-o(1)}$ size.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。