Graph Matching via the Projected Power Method and Mirror Descent
Speaker: Ernesto Araya
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 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. References: https://www.jmlr.org/papers/volume25/22-0402/22-0402.pdf https://arxiv.org/abs/2310.20609