  Graph matching problem aims to identify node correspondence between two or
more correlated graphs. Previous studies have primarily focused on models where
only edge information is provided. However, in many social networks, not only
the relationships between users, represented by edges, but also their personal
information, represented by features, are present. In this paper, we address
the challenge of identifying node correspondence in correlated graphs, where
additional node features exist, as in many real-world settings. We propose a
two-step procedure, where we initially match a subset of nodes only using edge
information, and then match the remaining nodes using node features. We derive
information-theoretic limits for exact graph matching on this model. Our
approach provides a comprehensive solution to the real-world graph matching
problem by providing systematic ways to utilize both edge and node information
for exact matching of the graphs.
