Random Graph Matching at Otter's Threshold via Counting Chandeliers

• 成果类型: Article; Early Access
• 署名作者: Mao, Cheng; Wu, Yihong; Xu, Jiaming; Yu, Sophie H.
• 署名单位: University System of Georgia; Georgia Institute of Technology; Yale University; Duke University; University of Pennsylvania
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0574
• 发表日期: 2025
• 关键词: alignment

摘要

We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdos-Renyi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq -> infinity and the edge correlation coefficient rho satisfies rho(2) > alpha approximate to 0:338, where alpha is Otter's tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is informationtheoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require rho = 1 - o(1) or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees.