Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory
Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Z. Fan;Cheng Mao;Yihong Wu;Jiaming Xu
中科院分区：
文献类型：
--
作者：
Z. Fan;Cheng Mao;Yihong Wu;Jiaming Xu
图匹配，也称为网络对齐，旨在恢复两个无标记且边相关的加权图之间潜在的顶点对应关系。为了解决这个任务，我们提出了一种谱方法，即通过成对特征向量对齐进行图匹配（GRAMPA），该方法首先构建一个相似性矩阵，作为两个图的所有特征向量对的外积的加权和，然后通过一个简单的取整过程输出一个匹配。对于相关的维格纳模型的一个普适类，GRAMPA在边相关性为\(1 - 1 / \text{多对数}(n)\)且平均度至少为\(\text{多对数}(n)\)的情况下，实现了两个图之间潜在匹配的精确恢复。这与为相关的厄尔多斯 - 仁伊图建立的多项式时间算法的现有最佳保证相匹配，并且显著优于现有的谱方法。GRAMPA的优越性在各种合成数据集和真实数据集上也得到了证明，无论是在统计准确性还是在计算效率方面。
Graph matching, also known as network alignment, aims at recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. To tackle this task, we propose a spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), which first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, and then outputs a matching by a simple rounding procedure. For a universality class of correlated Wigner models, GRAMPA achieves exact recovery of the latent matching between two graphs with edge correlation 1 − 1 / polylog( n ) and average degree at least polylog( n ) . This matches the state-of-the-art guarantees for polynomial-time algorithms established for correlated Erd˝os-R´enyi graphs, and significantly improves over existing spectral meth-ods. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency.