From tree matching to sparse graph alignment

Abstract

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 that the algorithm returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in $O(1)$ and correlation parameter $s$ that can be bounded away from 1, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent.

arXiv comment33 pages, 10 figures, accepted at COLT 2020. Typos corrected, some new figures, some remarks and explanations detailed, minor changes in proof of Th. 1.2

Cited by in corpus (7)

• Testing network correlation efficiently via counting trees
• Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
• Testing correlation of unlabeled random graphs
• Graph Matching with Partially-Correct Seeds
• Correlation detection in trees for planted graph alignment
• Exact Matching of Random Graphs with Constant Correlation
• Random Graph Matching with Improved Noise Robustness