Random Graph Matching with Improved Noise Robustness
Random Graph Matching with Improved Noise Robustness
复制标题
DOI：
--
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Cheng Mao;M. Rudelson;K. Tikhomirov
中科院分区：
文献类型：
--
作者：
Cheng Mao;M. Rudelson;K. Tikhomirov
图匹配，也称为网络对齐，是指找到两个给定图的顶点集之间的双射，以便最大限度地对齐它们的边。这个基本的计算问题经常出现在计算机视觉和生物学等多个领域。最近，已经有大量的工作研究有效的算法下的概率模型图匹配。在这项工作中，我们提出了一个新的算法图匹配：我们的算法相关联的每个顶点与一个签名向量使用一个多阶段的过程，然后匹配一对顶点从两个图，如果他们的签名向量彼此接近。我们证明了，对于两个边相关度为1-\alpha$的Erd\H{o} s-R\'enyi图，当$\alpha \le 1 /（\log \log n）^C$时，我们的算法以很高的概率精确地恢复了潜在的匹配，其中$n$是每个图中的顶点数，$C$表示一个正的泛常数.这改进了在以前的工作中实现的条件$\alpha \le 1 /（\log n）^C$。
Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erd\H{o}s--R\'enyi graphs with edge correlation $1-\alpha$, our algorithm recovers the underlying matching exactly with high probability when $\alpha \le 1 / (\log \log n)^C$, where $n$ is the number of vertices in each graph and $C$ denotes a positive universal constant. This improves the condition $\alpha \le 1 / (\log n)^C$ achieved in previous work.