  In this paper, the problem of matching pairs of correlated random graphs with
multi-valued edge attributes is considered. Graph matching problems of this
nature arise in several settings of practical interest including social network
de-anonymization, study of biological data, web graphs, etc. An achievable
region for successful matching is derived by analyzing a new matching algorithm
that we refer to as typicality matching. The algorithm operates by
investigating the joint typicality of the adjacency matrices of the two
correlated graphs. Our main result shows that the achievable region depends on
the mutual information between the variables corresponding to the edge
probabilities of the two graphs. The result is based on bounds on the
typicality of permutations of sequences of random variables that might be of
independent interest.
