Seeded Graph Matching via Large Neighborhood Statistics
This work provides a significant improvement for seeded graph matching, with potential applications in network alignment and data integration, though it is incremental over prior results.
The paper tackles the problem of recovering vertex correspondence between edge-correlated Erdős-Rényi random graphs with initial seed information, achieving the information-theoretic limit of graph sparsity in polynomial time and reducing seed requirements to as low as n^{3ε} in sparse regimes and Ω(log n) in dense regimes.
We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated Erdős-Rényi random graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. For seeded problems, our result provides a significant improvement over previously known results. We show that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of vertices $n$. Moreover, we show the number of seeds needed for exact recovery in polynomial-time can be as low as $n^{3ε}$ in the sparse graph regime (with the average degree smaller than $n^ε$) and $Ω(\log n)$ in the dense graph regime. Our results also shed light on the unseeded problem. In particular, we give sub-exponential time algorithms for sparse models and an $n^{O(\log n)}$ algorithm for dense models for some parameters, including some that are not covered by recent results of Barak et al.