Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)
This work addresses the challenge of graph matching for researchers in network analysis and inference, offering a novel solution that is incremental in improving alignment accuracy without edge correlation.
The authors tackled the problem of aligning vertices across multiple networks without relying on edge correlation, introducing the OmniMatch algorithm which asymptotically and efficiently perfectly aligns O(s^α) unseeded vertices in Random Dot Product Graphs under mild assumptions. They demonstrated its effectiveness in simulations and applications like shuffled graph hypothesis testing, where it recovered lost testing power by correcting misaligned vertices.
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, OmniMatch with $s$ seeds asymptotically and efficiently perfectly aligns $O(s^α)$ unseeded vertices -- for $α<2\wedge d/4$ -- across multiple networks even in the presence of no edge correlation. We demonstrate the effectiveness of our algorithm 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 we demonstrate the capacity of OmniMatch to correct for misaligned vertices prior to testing and hence recover the lost testing power. We further demonstrate the algorithm on a pair of data examples from connectomics and machine translation.