Seeded graph matching via large neighborhood statistics. Issue 3 (30th June 2020)

• Record Type: Journal Article
• Authors: Mossel, Elchanan; Xu, Jiaming
• Is Part Of: Random structures & algorithms. Volume 57:Issue 3(2020)
• Page Start: 570
• Page End: 611
• Publication Date: 2020-06-30
• Subjects: branching process -- graph isomorphism -- graph matching -- subgraph count; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20934
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge‐correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. 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 perfect recovery in polynomial‐time can be as low as n ϵ in the sparse graph regime (with the average degree smaller than n ϵ ) and Ω ( log n ) in the dense graph regime, for a small positive constant ϵ . Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.