Graph Matching via the Projected Power Method and Mirror Descent

In the Graph Matching (also known as Network Alignment) problem, the goal is to find a shared vertex labeling (matching) between two observed, unlabelled graphs, focusing on maximizing the alignment of their edges. This problem can be framed as a random instance of the well-known quadratic assignment problem. We explore two versions of graph matching: the seeded version, where partial matching is provided as side information, and the seedless version, where only the input graphs are given. For the seeded case, we introduce a statistically guaranteed algorithm based on the projected power method and demonstrate its effectiveness in the correlated Gaussian Wigner model, a widely used generative framework for jointly generated graphs. For the seedless case, we propose a novel convex relaxation approach combined with a Mirror Descent algorithm, demonstrating its capability to recover the ground truth matching in the case of isomorphic input graphs.