  Graph alignment aims at finding the vertex correspondence between two
correlated graphs, a task that frequently occurs in graph mining applications
such as social network analysis. Attributed graph alignment is a variant of
graph alignment, in which publicly available side information or attributes are
exploited to assist graph alignment. Existing studies on attributed graph
alignment focus on either theoretical performance without computational
constraints or empirical performance of efficient algorithms. This motivates us
to investigate efficient algorithms with theoretical performance guarantee. In
this paper, we propose two polynomial-time algorithms that exactly recover the
vertex correspondence with high probability. The feasible region of the
proposed algorithms is near optimal compared to the information-theoretic
limits. When specialized to the seeded graph alignment problem under the seeded
Erd\H{o}s--R\'{e}nyi graph pair model, the proposed algorithms extends the best
known feasible region for exact alignment by polynomial-time algorithms.
