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.