Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.02825 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912461543702528 |
|---|---|
| author | Qi, Tong Andersson, Vera Viechnicki, Peter Lyzinski, Vince |
| author_facet | Qi, Tong Andersson, Vera Viechnicki, Peter Lyzinski, Vince |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_02825 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotically perfect seeded graph matching without edge correlation (and applications to inference) Qi, Tong Andersson, Vera Viechnicki, Peter Lyzinski, Vince Machine Learning 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. |
| title | Asymptotically perfect seeded graph matching without edge correlation (and applications to inference) |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2506.02825 |