  Driven by many real applications, we study the problem of seeded graph
matching. Given two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, and a
small set $S$ of pre-matched node pairs $[u, v]$ where $u \in V_1$ and $v \in
V_2$, the problem is to identify a matching between $V_1$ and $V_2$ growing
from $S$, such that each pair in the matching corresponds to the same
underlying entity. Recent studies on efficient and effective seeded graph
matching have drawn a great deal of attention and many popular methods are
largely based on exploring the similarity between local structures to identify
matching pairs. While these recent techniques work well on random graphs, their
accuracy is low over many real networks. Motivated by this, we propose to
utilize high order neighboring information to improve the matching accuracy. As
a result, a new framework of seeded graph matching is proposed, which employs
Personalized PageRank (PPR) to quantify the matching score of each node pair.
To further boost the matching accuracy, we propose a novel postponing strategy,
which postpones the selection of pairs that have competitors with similar
matching scores. We theoretically prove that the postpone strategy indeed
significantly improves the matching accuracy. To improve the scalability of
matching large graphs, we also propose efficient approximation techniques based
on algorithms for computing PPR heavy hitters. Our comprehensive experimental
studies on large-scale real datasets demonstrate that, compared with state of
the art approaches, our framework not only increases the precision and recall
both by a significant margin but also achieves speed-up up to more than one
order of magnitude.
