Exact matching of random graphs with constant correlation

• 成果类型: Article
• 署名作者: Mao, Cheng; Rudelson, Mark; Tikhomirov, Konstantin
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Michigan System; University of Michigan
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-022-01184-3
• 发表日期: 2023
• 页码: 327-389

摘要

This paper deals with the problem of graph matching or network alignment for Erdos- Renyi graphs, which can be viewed as a noisy average-case version of the graph isomorphism problem. Let G and G' be G(n, p) Erdos-Renyi graphs marginally, identified with their adjacency matrices. Assume that G and G' are correlated such that E[G(ij)G'(ij)] = p(1 - alpha). For a permutation pi representing a latent matching between the vertices of G and G', denote by G(pi) the graph obtained from permuting the vertices of G by pi. Observing G(pi) and G', we aim to recover the matching pi. In this work, we show that for every epsilon is an element of (0, 1], there is n(0) > 0 depending on epsilon and absolute constants alpha(0), R > 0 with the following property. Let n >= n(0), (1 + epsilon) log n <= 1 np <= n 1/R log log n , and 0 < alpha < min(alpha(0), epsilon /4). There is a polynomial-time algorithm F such that P{F(G(pi), G') = pi} = 1 - o(1). This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated Erdos-Renyi graphs with constant correlation with high probability. The algorithm is based on comparison of partition trees associated with the graph vertices.