Graph Matching via the Projected Power Method and Mirror Descent.
| When |
Feb 06, 2024
from 01:00 to 02:00 |
|---|---|
| Attendees |
Ernesto Araya Valdivia |
| Add event to calendar |
vCal
iCal
|
Ernesto Araya Valdivia
Title: Graph Matching via the Projected Power Method and Mirror Descent.
Abstract: In the Graph Matching (aka Network Alignment) problem, our objective is to uncover a shared vertex labeling (matching) between two observed, unlabelled graphs, with a focus on maximizing the alignment of their edges. This task can be aptly formalized as an instance of the renowned quadratic assignment problem. We explore two variants of graph matching: the seeded version, characterized by the availability of partial matching as side information, and the seedless version, where only the input graphs are provided. For the seeded version, we present a statistically guaranteed algorithm based on the projected power method and demonstrate its effectiveness when the two graphs are jointly generated using the correlated Gaussian Wigner model. In the seedless version, we introduce a novel convex relaxation approach alongside a Mirror Descent algorithm, demonstrating its ability to recover ground truth matching, in the scenario that the input graphs are isomorphic.
This talk is based in joint work with Guillaume Braun and Hemant Tyagi.
Website: https://scholar.google.co.uk/citations?user=kXD5AegAAAAJ&hl=nl