  In this paper, matching pairs of stocahstically generated graphs in the
presence of generalized seed side-information is considered. The graph matching
problem emerges naturally in various applications such as social network
de-anonymization, image processing, DNA sequencing, and natural language
processing. A pair of randomly generated labeled Erdos-Renyi graphs with
pairwise correlated edges are considered. It is assumed that the matching
strategy has access to the labeling of the vertices in the first graph, as well
as a collection of shortlists -- called ambiguity sets -- of possible labels
for the vertices of the second graph. The objective is to leverage the
correlation among the edges of the graphs along with the side-information
provided in the form of ambiguity sets to recover the labels of the vertices in
the second graph. This scenario can be viewed as a generalization of the seeded
graph matching problem, where the ambiguity sets take a specific form such that
the exact labels for a subset of vertices in the second graph are known prior
to matching. A matching strategy is proposed which operates by evaluating the
joint typicality of the adjacency matrices of the graphs. Sufficient conditions
on the edge statistics as well as ambiguity set statistics are derived under
which the proposed matching strategy successfully recovers the labels of the
vertices in the second graph. Additionally, Fano-type arguments are used to
derive general necessary conditions for successful matching.
