(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

We consider the graph matching/similarity problem of determining how similar two given graphs G_0,G_1 are and recovering the permutation \pi on the vertices of G_1 that minimizes the symmetric difference between the edges of G_0 and \pi(G_1) . Graph matching/similarity has applications for pattern matching, vision, social network anonymization, malware analysis, and more. We give the first efficient algorithms proven to succeed in the correlated Erdös-Rényi model (Pedarsani and Grossglauser, 2011). Specifically, we give a polynomial time algorithm for the graph similarity/hypothesis testing task which works for every constant level of correlation between the two graphs that can be arbitrarily close to zero. We also give a quasi-polynomial ( n {O(\log n)} time) algorithm for the graph matching task of recovering the permutation minimizing the symmetric difference in this model.