Algorithmic analysis demonstrates polynomial-time matching in correlated Erdős–Rényi graphs at Otter's threshold, enabling efficient alignment across sparse and dense regimes.
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 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→∞ and the edge correlation coefficient ρ satisfies ρ2>α ≈ 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.
No takes yet. Share an insight, caveat, or question.
Mao et al. (2023) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: