Graph Matching via the Projected Power Method and Mirror Descent

Abstract

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 an 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 present a statistically guaranteed algorithm based on the projected power method and show its effectiveness when the two graphs are jointly generated using the correlated Gaussian Wigner model. 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.
This talk is based on joint work with Guillaume Braun and Hemant Tyagi.