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

arXiv: https://arxiv.org/abs/2204.04099 · HTML: https://mlsanity.com/paper/2204.04099/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 8 Apr 2022.

## Builds on (most cited first, 27 of 27)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2007.00533/) (2020)
- [From tree matching to sparse graph alignment](https://mlsanity.com/paper/2002.01258/) (2020)
- [Higher-order Projected Power Iterations for Scalable Multi-Matching](https://mlsanity.com/paper/1811.10541/) (2018)
- [Exact Matching of Random Graphs with Constant Correlation](https://mlsanity.com/paper/2110.05000/) (2021)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences](https://mlsanity.com/paper/1609.05820/) (2016)
- [Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm](https://mlsanity.com/paper/1403.7721/) (2014)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [Strong recovery of geometric planted matchings](https://mlsanity.com/paper/2107.05567/) (2021)
- [Graph Matching with Partially-Correct Seeds](https://mlsanity.com/paper/2004.03816/) (2020)
- [Optimal Non-Convex Exact Recovery in Stochastic Block Model via Projected Power Method](https://mlsanity.com/paper/2106.05644/) (2021)
- [The Power of D-hops in Matching Power-Law Graphs](https://mlsanity.com/paper/2102.12975/) (2021)
- [Spectral Alignment of Correlated Gaussian matrices](https://mlsanity.com/paper/1912.00231/) (2019)
- [Optimal Orthogonal Group Synchronization and Rotation Group Synchronization](https://mlsanity.com/paper/2109.13491/) (2021)
- [On the Structure and Efficient Computation of IsoRank Node Similarities](https://mlsanity.com/paper/1602.00668/) (2016)
- [Projected Power Iteration for Network Alignment](https://mlsanity.com/paper/1707.04929/) (2017)
- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)

## Built on by (most cited first, 4 of 4)

- [Graph Matching via convex relaxation to the simplex](https://mlsanity.com/paper/2310.20609/) (2023)
- [The graph alignment problem: fundamental limits and efficient algorithms](https://mlsanity.com/paper/2404.12418/) (2024)
- [On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA](https://mlsanity.com/paper/2312.03438/) (2023)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)

## Abstract (arXiv)

In the 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 σ∈ [0,1). In this paper, we analyse the performance of the projected power method (PPM) as a 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 O(log n) iterations. Our results prove that PPM works even in regimes of constant σ, 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.