Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis
Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis
复制标题
DOI：
10.1007/s10208-022-09570-y
复制
发表时间：
2022-06
影响因子：
3
通讯作者：
Z. Fan;Cheng Mao;Yihong Wu;Jiaming Xu
中科院分区：
文献类型：
--
作者：
Z. Fan;Cheng Mao;Yihong Wu;Jiaming Xu
图匹配的目的是找到两个未标记图之间的顶点对应关系，从而最大化总边权重相关性。这相当于解决计算上难以处理的二次分配问题。在本文中，我们提出了一种新的谱方法，即通过成对特征对齐进行图匹配（GRAMPA）。与仅比较顶部特征向量或相同阶特征向量的现有谱方法不同，GRAMPA 首先构造一个相似性矩阵，作为两个图的所有特征向量对之间的外积的加权和，并将柯西核给出的权重应用于相应特征值的分离，然后通过简单的舍入过程输出匹配。相似度矩阵也可以解释为二次分配问题的正则化二次规划松弛的解。对于高斯维格纳模型，其中两个顶点上的完整图具有具有相关系数的高斯边权重，我们证明了 GRAMPA 能够以高概率准确地恢复正确的顶点对应关系。这符合多项式时间算法的最新技术，并且显着改进了需要多项式小旅馆的现有谱方法。 GRAMPA 在统计准确性和计算效率方面的优越性也在各种合成和真实数据集上得到了证明。普遍性结果，包括对密集和稀疏 Erdős-Rényi 图的类似保证，推迟到另一篇论文中。
Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper, we propose a new spectral method, graph matching by pairwise eigen-alignments (GRAMPA). Departing from prior spectral approaches that only compare top eigenvectors, or eigenvectors of the same order, GRAMPA first constructs a similarity matrix as a weighted sum of outer products betweenallpairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. For the Gaussian Wigner model in which two complete graphs onnvertices have Gaussian edge weights with correlation coefficient, we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when. This matches the state of the art of polynomial-time algorithms and significantly improves over existing spectral methods which requireto be polynomially small inn. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. Universality results, including similar guarantees for dense and sparse Erdős–Rényi graphs, are deferred to a companion paper.