On the Performance of a Canonical Labeling for Matching Correlated Erd\H{o}s-R\'enyi Graphs

Graph matching (GM) (also called graph alignment or network reconciliation) refers to a class of computational techniques to identify node correspondences across related networks based on structural information. GM has applications in a variety of domains, including data fusion, privacy, computer vision, and in computational biology. For example, in computational biology, a coarse description of the metabolic machinery of a particular species is via a protein-protein interaction (PPI) network, which essentially captures which protein can react with which other protein in that species. Across species, the PPI networks tend to be strongly correlated, because evolution transfers metabolic processes from species to species. Therefore, by identifying correspondences among proteins in different species (so-called orthologs), one is able to transfer biological knowledge from one species to the other. However, crucially, the actual proteins tend to be chemically different across species, because random mutations alter these proteins over time without affecting their function. It is therefore not possible to find correspondences between proteins in different species simply by examining their amino-acid sequences. GM computes such correspondences by exploiting the correlation across networks in different species. A similar challenge arises in social networks: suppose a set of users have accounts in several social networks.