From tree matching to sparse graph alignment

Luca Ganassali, Laurent Massoulié

In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-Rényi random graphs, we prove tha…