Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing

원문 초록

This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erd\H{o}s-R\'enyi graphs without any incorrect matches. Each graph has average degree $\lambda$ and its edges are subsampled from a common parent Erd\H{o}s-R\'enyi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $\lambda=\omega(1)$ with $\lambda=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $\lambda s\ge(1+\epsilon)\log n$ for a constant $\epsilon>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.