From tree matching to sparse graph alignment

In this paper we consider alignment of sparse graphs, for which we introduce\nthe Neighborhood Tree Matching Algorithm (NTMA). For correlated\nErd\\H{o}s-R\\'{e}nyi random graphs, we prove that the algorithm returns -- in\npolynomial time -- a positive fraction of correctly matched vertices, and a\nvanishing fraction of mismatches. This result holds with average degree of the\ngraphs in $O(1)$ and correlation parameter $s$ that can be bounded away from 1,\nconditions under which random graph alignment is particularly challenging. As a\nbyproduct of the analysis we introduce a matching metric between trees and\ncharacterize it for several models of correlated random trees. These results\nmay be of independent interest, yielding for instance efficient tests for\ndetermining whether two random trees are correlated or independent.\n