论文标题
通过计数吊灯在水獭阈值处随机匹配
Random graph matching at Otter's threshold via counting chandeliers
论文作者
论文摘要
我们根据计算植根于每个顶点的某个加权树系列而构成的相似性分数提出了一种有效的图形匹配算法。对于两个Erdős-rényi图$ \ Mathcal {g}（n，q）$，其边缘通过潜在顶点对应关系相关，我们表明，该算法正确地匹配了顶点的所有范围，但最高的可能性与较高的可能性匹配，前提是，只要$ nq \ y $ nq \ y y quftty $ nq of the Edge unfty $ $ $ $ $ @ 0.338 $，其中$α$是Otter的树木计数常数。此外，在理论上是必需的额外条件下，可以精确地匹配这种几乎确切的匹配。这是第一个以显式常数相关性成功的多项式图匹配算法，并适用于稀疏和密集图。相比之下，以前的方法要么需要$ρ= 1-o（1）$，要么仅限于稀疏图。 该算法的症结是一个经过精心策划的植根树的家族，称为枝形吊灯，它允许从同一树的计数中提取图形相关性，同时抑制不同树木之间的不良相关性。
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 Erdős-Rényi graphs $\mathcal{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\to\infty$ and the edge correlation coefficient $ρ$ satisfies $ρ^2>α\approx 0.338$, where $α$ is Otter's tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically 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 $ρ=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.
