无需边相关性，用种子点实现多图完美对齐。
Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)
- 基于随机点积图模型，用种子点引导多图匹配
- 可对齐约O(s^α)个无种子顶点，α<2∧d/4
- 适合连接组学、机器翻译等跨网络推断任务
我们提出OmniMatch算法用于带种子的多图匹配。在d维随机点积图（RDPG）设定下，在合理假设下，即使无边相关性，该算法也能在渐近意义上高效地完美对齐多达O(s^α)个无种子顶点（其中α<2∧d/4）。我们在多种模拟实验及乱序图假设检验场景中验证了算法有效性：乱序导致检验效能下降，而OmniMatch能先纠正顶点错位，恢复检验能力。此外，我们在连接组学和机器翻译两组真实数据上展示了该方法的应用价值。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。