A0935
Title: Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)
Authors: Tong Qi - University of Maryland (United States)
Peter Viechnicki - Johns Hopkins University (United States)
Vera Andersson - University of Maryland (United States)
Vince Lyzinski - University of Maryland, College Park (United States) [presenting]
Abstract: The OmniMatch algorithm is presented for seeded multiple graph matching. In the setting of d-dimensional random dot product graphs (RDPG), it is proven that under mild assumptions, OmniMatch with s seeds asymptotically and efficiently perfectly aligns $O(s^x)$ unseeded vertices, for $x<2d/4$, across multiple networks even in the presence of no edge correlation. The effectiveness of the algorithm is demonstrated across numerous simulations and in the context of shuffled graph hypothesis testing. In the shuffled testing setting, testing power is lost due to the misalignment/shuffling of vertices across graphs, and the capacity of OmniMatch is demonstrated to correct for misaligned vertices prior to testing and hence recover the lost testing power. The algorithm is further demonstrated on a pair of data examples from connectomics and machine translation.
