Seeded graph matching for the correlated Gaussian Wigner model via the projected power method

Abstract

In the \emph{graph matching} problem we observe two graphs $G,H$ and the goal is to find an assignment (or matching) between their vertices such that some measure of edge agreement is maximized. We assume in this work that the observed pair $G,H$ has been drawn from the Correlated Gaussian Wigner (CGW) model -- a popular model for correlated weighted graphs -- where the entries of the adjacency matrices of $G$ and $H$ are independent Gaussians and each edge of $G$ is correlated with one edge of $H$ (determined by the unknown matching) with the edge correlation described by a parameter $\sigma \in [0,1)$. In this paper, we analyse the performance of the \emph{projected power method} (PPM) as a \emph{seeded} graph matching algorithm where we are given an initial partially correct matching (called the seed) as side information. We prove that if the seed is close enough to the ground-truth matching, then with high probability, PPM iteratively improves the seed and recovers the ground-truth matching (either partially or exactly) in $\mathcal{O}(\log n)$ iterations. Our results prove that PPM works even in regimes of constant $\sigma$, thus extending the analysis in (Mao et al. 2023) for the sparse Correlated Erdos-Renyi(CER) model to the (dense) CGW model. As a byproduct of our analysis, we see that the PPM framework generalizes some of the state-of-art algorithms for seeded graph matching. We support and complement our theoretical findings with numerical experiments on synthetic data.

References in corpus (15)

• De-anonymizing Social Networks
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Powers of Tensors and Fast Matrix Multiplication
• Nonconvex phase synchronization
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Graph Matching with Partially-Correct Seeds
• On the Structure and Efficient Computation of IsoRank Node Similarities
• Random Graph Matching in Geometric Models: the Case of Complete Graphs
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method
• The Power of $D$-hops in Matching Power-Law Graphs
• Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• Exact Community Recovery over Signed Graphs