Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in the companion paper for Gaussian weights, in this work, we prove the universality of these guarantees for a general correlated Wigner model. In particular, for two Erd\H{o}s-R\'enyi graphs with edge correlation coefficient $1-\sigma^2$ and average degree at least $\operatorname{polylog}(n)$, we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when $\sigma \lesssim 1/\operatorname{polylog}(n)$. Moreover, we establish a similar guarantee for a variant of GRAMPA, corresponding to a tighter quadratic programming relaxation of the quadratic assignment problem. Our analysis exploits a resolvent representation of the GRAMPA similarity matrix and local laws for the resolvents of sparse Wigner matrices.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
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. …
Computational EfficiencyGraph MatchingSpectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory
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 Matchi…
Computational EfficiencyGraph MatchingDS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems
In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong dis…
Graph MatchingFRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing
Graph matching, typically formulated as a Quadratic Assignment Problem (QAP), seeks to establish node correspondences between two graphs. To address the NP-hardness of QAP, some existing methods adopt projection-based re…
Graph MatchingSparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation
We address the non-convex optimisation problem of finding a sparse matrix on the Stiefel manifold (matrices with mutually orthogonal columns of unit length) that maximises (or minimises) a quadratic objective function. O…
ClusteringConstrained ClusteringGraph Matching