Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)

Tong Qi, Vera Andersson, Peter Viechnicki +1

We present the OmniMatch algorithm for seeded multiple graph matching. In the setting of $d$-dimensional Random Dot Product Graphs (RDPG), we prove that under mild assumptions, Omn…